Task: | Ruudukko |
Sender: | Metabolix |
Submission time: | 2020-11-08 21:59:50 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 45 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 5 |
#2 | ACCEPTED | 12 |
#3 | WRONG ANSWER | 0 |
#4 | ACCEPTED | 28 |
#5 | WRONG ANSWER | 0 |
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 | WRONG ANSWER | 0.01 s | 3, 5 | details |
#10 | ACCEPTED | 0.01 s | 3, 5 | details |
#11 | WRONG ANSWER | 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 | WRONG ANSWER | 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 ((y1 == 0 || y1 == l.h - 1) && x1 == 1 && l.w == 3) { return false; } if ((x1 == 0 || x1 == l.w - 1) && y1 == 1 && l.h == 3) { return false; } if (l.w > 5) { 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) { 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: WRONG ANSWER
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 NO NO ... 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: WRONG ANSWER
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: WRONG ANSWER
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 |