Task: | Ruudukko |
Sender: | Metabolix |
Submission time: | 2020-11-08 22:01:29 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 5 |
#2 | ACCEPTED | 12 |
#3 | ACCEPTED | 27 |
#4 | ACCEPTED | 28 |
#5 | ACCEPTED | 28 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 5 | details |
#2 | ACCEPTED | 0.01 s | 2, 5 | details |
#3 | ACCEPTED | 0.01 s | 3, 5 | details |
#4 | ACCEPTED | 0.01 s | 4, 5 | details |
#5 | ACCEPTED | 0.01 s | 5 | details |
#6 | ACCEPTED | 0.01 s | 5 | details |
#7 | ACCEPTED | 0.01 s | 2, 5 | details |
#8 | ACCEPTED | 0.01 s | 2, 5 | details |
#9 | ACCEPTED | 0.01 s | 3, 5 | details |
#10 | ACCEPTED | 0.01 s | 3, 5 | details |
#11 | ACCEPTED | 0.01 s | 3, 5 | details |
#12 | ACCEPTED | 0.01 s | 3, 5 | details |
#13 | ACCEPTED | 0.01 s | 4, 5 | details |
#14 | ACCEPTED | 0.01 s | 5 | details |
#15 | ACCEPTED | 0.01 s | 3, 5 | details |
#16 | ACCEPTED | 0.02 s | 5 | details |
Code
#include <bits/stdc++.h>struct lauta {char t[50][51] = {{0}};char& xy(int x, int y) {return t[y][x];}};struct lautaref {lauta* l;int x0, y0, w, h;char& xy(int x, int y) {return l->xy(x0 + x, y0 + y);}lautaref pala(int x0_, int y0_, int w_, int h_) {assert(x0_ >= 0);assert(y0_ >= 0);assert(w_ - x0_ <= w);assert(h_ - y0_ <= h);return lautaref {l, x0 + x0_, y0 + y0_, w_, h_};}};bool dfs(lautaref l, int x1, int y1, int x2, int y2, int lkm) {if (x1 == x2 && y1 == y2 && lkm == 0) {return true;}#define F(dx, dy, m) \if (0 <= x1 + (dx) && x1 + (dx) < l.w && 0 <= y1 + (dy) && y1 + (dy) < l.h && l.xy(x1 + (dx), y1 + (dy)) == 0) { \l.xy(x1, y1) = m; \if (dfs(l, x1 + (dx), y1 + (dy), x2, y2, lkm - 1)) return true; \}F(0, -1, 'U')F(0, 1, 'D')F(-1, 0, 'L')F(1, 0, 'R')l.xy(x1, y1) = 0;return false;}void viivaX(lautaref l, int x0, int x1, int y, char c) {while (x0 != x1) {l.xy(x0, y) = c;x0 += x0 < x1 ? 1 : -1;}l.xy(x0, y) = c;}void viivaY(lautaref l, int x, int y0, int y1, char c) {while (y0 != y1) {l.xy(x, y0) = c;y0 += y0 < y1 ? 1 : -1;}l.xy(x, y0) = c;}void kehaLURD(lautaref l) {viivaX(l, 0, l.w - 2, 0, 'R');viivaY(l, l.w - 1, 0, l.h - 2, 'D');viivaX(l, 1, l.w - 1, l.h - 1, 'L');viivaY(l, 0, 1, l.h - 1, 'U');}void kehaLDRU(lautaref l) {viivaX(l, 1, l.w - 1, 0, 'L');viivaY(l, l.w - 1, 1, l.h - 1, 'U');viivaX(l, 0, l.w - 2, l.h - 1, 'R');viivaY(l, 0, 0, l.h - 2, 'D');}void yla2(lautaref l) {for (int i = 0; i < l.w; ++i) {if (l.xy(i, 2) == 'R') {kehaLURD(l.pala(0, 0, l.w, 2));l.xy(i, 2) = 'U';l.xy(i+1, 1) = 'D';return;}if (l.xy(i, 2) == 'L') {kehaLDRU(l.pala(0, 0, l.w, 2));l.xy(i, 2) = 'U';l.xy(i-1, 1) = 'D';return;}}}void ala2(lautaref l) {for (int i = 0; i < l.w; ++i) {if (l.xy(i, l.h - 3) == 'R') {kehaLDRU(l.pala(0, l.h - 2, l.w, 2));l.xy(i, l.h - 3) = 'D';l.xy(i+1, l.h - 2) = 'U';return;}if (l.xy(i, l.h - 3) == 'L') {kehaLURD(l.pala(0, l.h - 2, l.w, 2));l.xy(i, l.h - 3) = 'D';l.xy(i-1, l.h - 2) = 'U';return;}}}void vasen2(lautaref l) {for (int i = 0; i < l.h; ++i) {if (l.xy(2, i) == 'U') {kehaLURD(l.pala(0, 0, 2, l.h));l.xy(2, i) = 'L';l.xy(1, i-1) = 'R';return;}if (l.xy(2, i) == 'D') {kehaLDRU(l.pala(0, 0, 2, l.h));l.xy(2, i) = 'L';l.xy(1, i+1) = 'R';return;}}}void oikea2(lautaref l) {for (int i = 0; i < l.h; ++i) {if (l.xy(l.w - 3, i) == 'U') {kehaLDRU(l.pala(l.w - 2, 0, 2, l.h));l.xy(l.w - 3, i) = 'R';l.xy(l.w - 2, i-1) = 'L';return;}if (l.xy(l.w - 3, i) == 'D') {kehaLURD(l.pala(l.w - 2, 0, 2, l.h));l.xy(l.w - 3, i) = 'R';l.xy(l.w - 2, i+1) = 'L';return;}}}bool ratkaise(lautaref l, int x1, int y1, int x2, int y2) {assert(x1 >= 0);assert(y1 >= 0);assert(x2 >= 0);assert(y2 >= 0);assert(x1 < l.w);assert(y1 < l.h);assert(x2 < l.w);assert(y2 < l.h);if ((l.w * l.h % 2 == 0) ? (x1 + y1) % 2 == (x2 + y2) % 2 : (((x1 + y1) % 2) || ((x2 + y2) % 2))) {return false;}if (l.w > 5 && 2 <= x1 && 2 <= x2) {if (ratkaise(l.pala(2, 0, l.w - 2, l.h), x1 - 2, y1, x2 - 2, y2)) {vasen2(l);return true;}return false;}if (l.h > 5 && 2 <= y1 && 2 <= y2) {if (ratkaise(l.pala(0, 2, l.w, l.h - 2), x1, y1 - 2, x2, y2 - 2)) {yla2(l);return true;}return false;}if (l.w > 5 && x1 < l.w - 2 && x2 < l.w - 2) {if (ratkaise(l.pala(0, 0, l.w - 2, l.h), x1, y1, x2, y2)) {oikea2(l);return true;}return false;}if (l.h > 5 && y1 < l.h - 2 && y2 < l.h - 2) {if (ratkaise(l.pala(0, 0, l.w, l.h - 2), x1, y1, x2, y2)) {ala2(l);return true;}return false;}if (l.w > 5) {if ((x1 == 0 || x1 == l.w - 1) && y1 == 1 && l.h == 3) {return false;}if ((x2 == 0 || x2 == l.w - 1) && y2 == 1 && l.h == 3) {return false;}if (x1 == 0) {if (y1 == 0) {kehaLDRU(l.pala(0, 0, 2, l.h));l.xy(1, 0) = 'R';return ratkaise(l.pala(2, 0, l.w - 2, l.h), 0, y1, x2 - 2, y2);}if (y1 == l.h - 1) {kehaLURD(l.pala(0, 0, 2, l.h));l.xy(1, y1) = 'R';return ratkaise(l.pala(2, 0, l.w - 2, l.h), 0, y1, x2 - 2, y2);}if (y1 == 1) {kehaLURD(l.pala(0, 0, 2, 3));kehaLDRU(l.pala(0, 2, 2, l.h - 2));l.xy(1, 3) = 'R';return ratkaise(l.pala(2, 0, l.w - 2, l.h), 0, y1 + 2, x2 - 2, y2);}if (y1 >= 2) {kehaLDRU(l.pala(0, y1 - 1, 2, l.h - y1 + 1));kehaLURD(l.pala(0, 0, 2, y1));l.xy(1, y1 - 2) = 'R';return ratkaise(l.pala(2, 0, l.w - 2, l.h), 0, y1 - 2, x2 - 2, y2);}}if (x1 == 1) {if (y1 == 0) {kehaLDRU(l.pala(0, 0, 2, l.h));l.xy(1, 1) = 'R';return ratkaise(l.pala(2, 0, l.w - 2, l.h), 0, 1, x2 - 2, y2);} else {kehaLURD(l.pala(0, 0, 2, l.h));l.xy(1, y1 - 1) = 'R';return ratkaise(l.pala(2, 0, l.w - 2, l.h), 0, y1 - 1, x2 - 2, y2);}}if (x1 == l.w - 1) {if (y1 == 0) {kehaLURD(l.pala(l.w - 2, 0, 2, l.h));l.xy(l.w - 2, 0) = 'L';return ratkaise(l.pala(0, 0, l.w - 2, l.h), x1 - 2, y1, x2, y2);}if (y1 == l.h - 1) {kehaLDRU(l.pala(l.w - 2, 0, 2, l.h));l.xy(l.w - 2, y1) = 'L';return ratkaise(l.pala(0, 0, l.w - 2, l.h), x1 - 2, y1, x2, y2);}if (y1 == 1) {kehaLDRU(l.pala(l.w - 2, 0, 2, 3));kehaLURD(l.pala(l.w - 2, 2, 2, l.h - 2));l.xy(l.w - 2, 3) = 'L';return ratkaise(l.pala(0, 0, l.w - 2, l.h), x1 - 2, y1 + 2, x2, y2);}if (y1 >= 2) {kehaLURD(l.pala(l.w - 2, y1 - 1, 2, l.h - y1 + 1));kehaLDRU(l.pala(l.w - 2, 0, 2, y1));l.xy(l.w - 2, y1 - 2) = 'L';return ratkaise(l.pala(0, 0, l.w - 2, l.h), x1 - 2, y1 - 2, x2, y2);}}if (x1 == l.w - 2) {if (y1 == 0) {kehaLURD(l.pala(l.w - 2, 0, 2, l.h));l.xy(l.w - 2, 1) = 'L';return ratkaise(l.pala(0, 0, l.w - 2, l.h), x1 - 1, 1, x2, y2);} else {kehaLDRU(l.pala(l.w - 2, 0, 2, l.h));l.xy(l.w - 2, y1 - 1) = 'L';return ratkaise(l.pala(0, 0, l.w - 2, l.h), x1 - 1, y1 - 1, x2, y2);}}}if (l.h > 5) {if ((y1 == 0 || y1 == l.h - 1) && x1 == 1 && l.w == 3) {return false;}if ((y2 == 0 || y2 == l.h - 1) && x2 == 1 && l.w == 3) {return false;}if (y1 == 0) {if (x1 == 0) {kehaLURD(l.pala(0, 0, l.w, 2));l.xy(0, 1) = 'D';return ratkaise(l.pala(0, 2, l.w, l.h - 2), x1, 0, x2, y2 - 2);}if (x1 == l.w - 1) {kehaLDRU(l.pala(0, 0, l.w, 2));l.xy(x1, 1) = 'D';return ratkaise(l.pala(0, 2, l.w, l.h - 2), x1, 0, x2, y2 - 2);}if (x1 == 1) {kehaLDRU(l.pala(0, 0, 3, 2));kehaLURD(l.pala(2, 0, l.w - 2, 2));l.xy(3, 1) = 'D';return ratkaise(l.pala(0, 2, l.w, l.h - 2), x1 + 2, 0, x2, y2 - 2);}if (x1 >= 2) {kehaLURD(l.pala(x1 - 1, 0, l.w - x1 + 1, 2));kehaLDRU(l.pala(0, 0, x1, 2));l.xy(x1 - 2, 1) = 'D';return ratkaise(l.pala(0, 2, l.w, l.h - 2), x1 - 2, 0, x2, y2 - 2);}}if (y1 == 1) {if (x1 == 0) {kehaLURD(l.pala(0, 0, l.w, 2));l.xy(1, 1) = 'D';return ratkaise(l.pala(0, 2, l.w, l.h - 2), 1, 0, x2, y2 - 2);} else {kehaLDRU(l.pala(0, 0, l.w, 2));l.xy(x1 - 1, 1) = 'D';return ratkaise(l.pala(0, 2, l.w, l.h - 2), x1 - 1, 0, x2, y2 - 2);}}if (y1 == l.h - 1) {if (x1 == 0) {kehaLDRU(l.pala(0, l.h - 2, l.w, 2));l.xy(0, l.h - 2) = 'U';return ratkaise(l.pala(0, 0, l.w, l.h - 2), x1, y1 - 2, x2, y2);}if (x1 == l.w - 1) {kehaLURD(l.pala(0, l.h - 2, l.w, 2));l.xy(x1, l.h - 2) = 'U';return ratkaise(l.pala(0, 0, l.w, l.h - 2), x1, y1 - 2, x2, y2);}if (x1 == 1) {kehaLURD(l.pala(0, l.h - 2, 3, 2));kehaLDRU(l.pala(2, l.h - 2, l.w - 2, 2));l.xy(3, l.h - 2) = 'U';return ratkaise(l.pala(0, 0, l.w, l.h - 2), x1 + 2, y1 - 2, x2, y2);}if (x1 >= 2) {kehaLDRU(l.pala(x1 - 1, l.h - 2, l.w - x1 + 1, 2));kehaLURD(l.pala(0, l.h - 2, x1, 2));l.xy(x1 - 2, l.h - 2) = 'U';return ratkaise(l.pala(0, 0, l.w, l.h - 2), x1 - 2, y1 - 2, x2, y2);}}if (y1 == l.h - 2) {if (x1 == 0) {kehaLDRU(l.pala(0, l.h - 2, l.w, 2));l.xy(1, l.h - 2) = 'U';return ratkaise(l.pala(0, 0, l.w, l.h - 2), 1, y1 - 1, x2, y2);} else {kehaLURD(l.pala(0, l.h - 2, l.w, 2));l.xy(x1 - 1, l.h - 2) = 'U';return ratkaise(l.pala(0, 0, l.w, l.h - 2), x1 - 1, y1 - 1, x2, y2);}}}if (l.h <= 5 && l.w <= 5) {return dfs(l, x1, y1, x2, y2, l.w * l.h - 1);}throw std::runtime_error("ratkaisu ei toimi");return false;}bool f(int h, int w, int y1, int x1, int y2, int x2) {if (h == 1) {if (x1 == 1 && x2 == w) {std::cout << "YES\n";while (x1 < x2) {std::cout << "R";++x1;}std::cout << "\n";return true;}if (x2 == 1 && x1 == w) {std::cout << "YES\n";while (x1 > x2) {std::cout << "L";--x1;}std::cout << "\n";return true;}std::cout << "NO\n";return false;}if (h == 2 && x1 == x2 && x1 != 1 && x1 != w) {std::cout << "NO\n";return false;}if (w == 2 && y1 == y2 && y1 != 1 && y1 != h) {std::cout << "NO\n";return false;}lauta l;int bugi = 0;try {if (!ratkaise(lautaref {&l, 0, 0, w, h}, x1 - 1, y1 - 1, x2 - 1, y2 - 1)) {std::cout << "NO\n";return false;}} catch (std::exception& e) {std::cout << e.what() << std::endl;bugi = 1;}std::cout << "YES\n";int x = x1, y = y1;for (int j = 1; j < w * h && !bugi; ++j) {std::cout << l.xy(x-1, y-1);switch (l.xy(x-1, y-1)) {case 'U': --y; break;case 'D': ++y; break;case 'L': --x; break;case 'R': ++x; break;default: bugi = 1;}}std::cout << "\n";if (x != x2 || y != y2 || bugi) {std::cout << h << ' ' << w << ' ' << y1 << ' ' << x1 << ' ' << y2 << ' ' << x2 << '\n';for (int i = 0; i < 50; ++i) for (int j = 0; j < 50; ++j) if (!l.xy(i,j)) l.xy(i,j) = ' ';for (int y = 0; y < h; ++y) {std::cout << l.t[y] << "\n";}std::cout << std::endl;abort();}return true;}int main() {int t = 0;std::cin >> t;if (!t) {for (int w = 2; w <= 15; ++w) for (int h = 2; h <= 15; ++h) {for (int x2 = 1; x2 <= w; ++x2) for (int x1 = 1; x1 <= w; ++x1) {for (int y2 = 1; y2 <= h; ++y2) for (int y1 = 1; y1 <= h; ++y1) if (x1 != x2 || y1 != y2) {bool mahdoton = (w * h % 2 == 0) ? (x1 + y1) % 2 == (x2 + y2) % 2 : (((x1 + y1) % 2) || ((x2 + y2) % 2));if (mahdoton) continue;f(h, w, y1, x1, y2, x2);}}}return 0;}for (int i = 0; i < t; ++i) {int h, w, y1, x1, y2, x2;if (std::cin >> h >> w >> y1 >> x1 >> y2 >> x2) {} else break;f(h, w, y1, x1, y2, x2);}}
Test details
Test 1
Group: 1, 5
Verdict: ACCEPTED
input |
---|
100 1 45 1 45 1 1 1 18 1 1 1 10 1 47 1 17 1 30 1 33 1 28 1 20 ... |
correct output |
---|
YES LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL... |
user output |
---|
YES LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL... Truncated |
Test 2
Group: 2, 5
Verdict: ACCEPTED
input |
---|
100 2 43 1 33 1 21 2 2 1 1 2 2 2 32 1 1 2 8 2 14 1 12 1 14 ... |
correct output |
---|
NO NO NO NO YES ... |
user output |
---|
NO NO NO NO YES ... Truncated |
Test 3
Group: 3, 5
Verdict: ACCEPTED
input |
---|
100 3 4 2 1 2 4 3 38 2 24 1 22 3 29 2 23 2 3 3 8 3 1 1 2 ... |
correct output |
---|
NO NO NO YES RRRRRRRUULDLULDLULDLLUR ... |
user output |
---|
NO NO NO YES RRRURDRURDRUULLLLLDLLUR ... Truncated |
Test 4
Group: 4, 5
Verdict: ACCEPTED
input |
---|
100 4 25 2 19 1 5 4 13 3 10 4 12 4 7 3 1 4 2 4 23 1 19 2 5 ... |
correct output |
---|
YES DDRRRRRRULLLLLURRRRRULLLLLLLDD... |
user output |
---|
YES RDDRUURDDRUURDDRUUULLLLLLLDDRD... Truncated |
Test 5
Group: 5
Verdict: ACCEPTED
input |
---|
100 16 8 13 1 14 8 41 21 19 11 32 12 46 17 13 7 6 11 8 41 4 32 4 12 ... |
correct output |
---|
NO YES LURULURULURULURULURRDDDDDDDDDR... |
user output |
---|
NO YES UUUUUUUUUUUUUUUUULDDDDDDDDDDDD... Truncated |
Test 6
Group: 5
Verdict: ACCEPTED
input |
---|
100 31 38 18 35 31 37 35 48 7 13 21 21 46 21 25 2 4 19 35 2 13 2 35 1 ... |
correct output |
---|
YES LLLLLLLLLLLLDRRRRRRRRRRRRDLLLL... |
user output |
---|
YES UUUUUUUUUUUUUUUULDDDDDDDDDDDDD... Truncated |
Test 7
Group: 2, 5
Verdict: ACCEPTED
input |
---|
100 2 4 1 3 1 4 2 4 2 2 1 1 2 4 2 3 1 2 2 4 2 3 1 4 ... |
correct output |
---|
YES LLDRRRU NO NO NO ... |
user output |
---|
YES LLDRRRU NO NO NO ... Truncated |
Test 8
Group: 2, 5
Verdict: ACCEPTED
input |
---|
100 2 5 1 2 2 4 2 5 1 2 1 1 2 5 2 1 1 2 2 5 1 1 1 5 ... |
correct output |
---|
YES LDRRURRDL YES RRRDLLLLU NO ... |
user output |
---|
YES LDRRURRDL YES RRRDLLLLU NO ... Truncated |
Test 9
Group: 3, 5
Verdict: ACCEPTED
input |
---|
100 3 4 1 1 2 3 3 4 2 4 3 2 3 4 2 1 3 1 3 4 1 4 3 4 ... |
correct output |
---|
YES DDRRRUULLDR NO YES URRRDDLULDL ... |
user output |
---|
YES DDRUURRDDLU NO YES URDRURDDLLL ... Truncated |
Test 10
Group: 3, 5
Verdict: ACCEPTED
input |
---|
100 3 5 3 4 3 2 3 5 3 5 2 3 3 5 3 1 2 2 3 5 3 1 3 2 ... |
correct output |
---|
NO NO YES UURRRRDDLULDLU NO ... |
user output |
---|
NO NO YES UURRDRURDDLLLU NO ... Truncated |
Test 11
Group: 3, 5
Verdict: ACCEPTED
input |
---|
100 3 8 2 8 1 2 3 8 2 4 1 7 3 8 3 4 2 7 3 8 2 5 3 1 ... |
correct output |
---|
NO NO NO YES LLLDRRRRURDRUULLLLLLLDD ... |
user output |
---|
NO NO NO YES DRURDRUULLLLDDLUULLDRDL ... Truncated |
Test 12
Group: 3, 5
Verdict: ACCEPTED
input |
---|
100 3 9 1 3 2 9 3 9 1 6 1 5 3 9 3 6 2 8 3 9 3 2 3 4 ... |
correct output |
---|
NO NO NO NO NO ... |
user output |
---|
NO NO NO NO NO ... Truncated |
Test 13
Group: 4, 5
Verdict: ACCEPTED
input |
---|
100 4 4 2 2 1 4 4 4 4 1 2 2 4 4 2 1 4 3 4 4 3 1 3 3 ... |
correct output |
---|
YES DDLUUURRDDDRUUU YES UUURRRDLDRDLLUU NO ... |
user output |
---|
YES ULDDDRURDRUULUR YES UUURRRDDDLLURUL NO ... Truncated |
Test 14
Group: 5
Verdict: ACCEPTED
input |
---|
100 12 27 6 22 1 8 6 25 3 2 4 4 6 16 4 6 5 2 36 33 8 6 1 6 ... |
correct output |
---|
YES DLDDDDDRUUUURDDDDRUURDDRRULURU... |
user output |
---|
YES RUUUURDDDDDDDDDDRUUUUUUUUUURDD... Truncated |
Test 15
Group: 3, 5
Verdict: ACCEPTED
input |
---|
100 3 12 3 5 1 4 3 20 3 19 2 19 3 34 3 9 2 9 3 38 2 15 3 15 ... |
correct output |
---|
YES RRRRRRRUULDLULDLULDLULDLDLULDL... |
user output |
---|
YES RURDRURDRURDRUULLLLLLLDLDLULDL... Truncated |
Test 16
Group: 5
Verdict: ACCEPTED
input |
---|
100 50 50 29 1 16 21 50 50 37 5 23 48 50 50 32 22 45 24 50 50 6 28 12 37 ... |
correct output |
---|
YES DDDDDDDDDDDDDDDDDDDDDRUUUUUUUU... |
user output |
---|
YES DDDDDDDDDDDDDDDDDDDDDRRRRRRRRR... Truncated |