Task: | Ruudukko |
Sender: | Olli |
Submission time: | 2020-11-07 22:12:39 +0200 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 67 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | ACCEPTED | 12 |
#3 | ACCEPTED | 27 |
#4 | ACCEPTED | 28 |
#5 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | WRONG ANSWER | 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.02 s | 5 | details |
#15 | ACCEPTED | 0.01 s | 3, 5 | details |
#16 | ACCEPTED | 0.04 s | 5 | details |
Compiler report
input/code.cpp: In function 'std::__cxx11::string mirror(std::__cxx11::string)': input/code.cpp:36:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int i = 0; i < s.size(); ++i) { ~~^~~~~~~~~~ input/code.cpp: In function 'std::__cxx11::string upsidedown(std::__cxx11::string)': input/code.cpp:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int i = 0; i < s.size(); ++i) { ~~^~~~~~~~~~ input/code.cpp: In function 'std::__cxx11::string rotate(std::__cxx11::string)': input/code.cpp:78:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int i = 0; i < s.size(); ++i) { ~~^~~~~~~~~~ input/code.cpp: In function 'std::__cxx11::string solve(int, int, int, int, int, int)': input/code.cpp:593:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int i = 0; i < s.size();...
Code
#include <iostream> #include <fstream> #include <vector> #include <algorithm> #include <queue> #include <stack> #include <set> #include <unordered_map> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define F first #define S second #define X first #define Y second const int N = 55; string mirror(string s) { for(int i = 0; i < s.size(); ++i) { if(s[i] == 'L') { s[i] = 'R'; } else if (s[i] == 'R') { s[i] = 'L'; } } return s; } string upsidedown(string s) { for(int i = 0; i < s.size(); ++i) { if(s[i] == 'U') { s[i] = 'D'; } else if (s[i] == 'D') { s[i] = 'U'; } } return s; } string reverse(string s) { if(s.size() == 0) return ""; string t = ""; for(int i = s.size() - 1; i >= 0; --i) { if(s[i] == 'D') { t += 'U'; } if(s[i] == 'U') { t += 'D'; } if(s[i] == 'L') { t += 'R'; } if(s[i] == 'R') { t += 'L'; } } return t; } string rotate(string s) { for(int i = 0; i < s.size(); ++i) { if(s[i] == 'D') { s[i] = 'L'; } else if (s[i] == 'R') { s[i] = 'U'; } else if (s[i] == 'U') { s[i] = 'R'; } else { s[i] = 'D'; } } return s; } bool z[N][N]; string cur; bool sol; string ans; int am; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; char di[4] = {'R', 'U', 'L', 'D'}; void dfs(int h, int w, int x2, int y2, int X, int Y) { if(sol) return; if(z[X][Y]) return; z[X][Y] = true; ++am; if(am == h*w) { ans = cur; sol = true; return; } for(int i = 0; i < 4; ++i) { int x = X + dx[i]; int y = Y + dy[i]; if(x == x2 && y == y2 && am != h*w - 1) { continue; } if(x <= 0 || x > w || y <= 0 || y > h) continue; cur += di[i]; dfs(h, w, x2, y2, x, y); cur.pop_back(); if(sol) break; } --am; z[X][Y] = false; } string solveBrute(int h, int w, int x1, int y1, int x2, int y2) { cur = ""; sol = false; ans = ""; for(int y = 1; y <= h; ++y) { for(int x = 1; x <= w; ++x) { z[x][y] = false; } } am = 0; dfs(h, w, x2, y2, x1, y1); return ans; } string solve(int h, int w, int x1, int y1, int x2, int y2) { if((h*w)%2 == 0) { if((x1 + x2 + y1 + y2)%2 == 0) return ""; } else { if((x1 + y1)%2 == 1 || (x2 + y2)%2 == 1) return ""; } if(h > w) { return rotate(solve(w, h, y1, x1, y2, x2)); } if(w <= 5) { return solveBrute(h, w, x1, y1, x2, y2); } if(h == 2) { if(y1 == 2) { return upsidedown(solve(h, w, x1, h+1-y1, x2, h+1-y2)); } //y1 = 1 if(x1 == x2) { if(x1 != 1 && x1 != w) { return ""; } if(x1 == w) return mirror(solve(h, w, w+1-x1, y1, w+1-x2, y2)); string s = ""; for(int i = 1; i <= w-1; ++i) { s += 'R'; } s += 'U'; for(int i = 1; i <= w-1; ++i) { s += 'L'; } return s; } if(x2 < x1) { return mirror(solve(h, w, w+1-x1, y1, w+1-x2, y2)); } if(y2 == 2) { if((x2-x1)%2 == 1) return ""; string s = ""; for(int i = 1; i <= x1 - 1; ++i) { s += "L"; } s += "U"; for(int i = 1; i <= x1; ++i) { s += "R"; } for(int i = 1; i <= (x2 - x1)/2 - 1; ++i) { s += "DRUR"; } s += "DR"; for(int i = 1; i <= (w - x2); ++i) { s += "R"; } s += "U"; for(int i = 1; i <= (w - x2); ++i) { s += "L"; } return s; } //y2 = 1 if((x2 - x1)%2 == 0) return ""; string s = ""; for(int i = 1; i <= x1 - 1; ++i) { s += "L"; } s += "U"; for(int i = 1; i <= x1-1; ++i) { s += "R"; } for(int i = 1; i <= (x2 - x1)/2; ++i) { s += "RDRU"; } s += "R"; for(int i = 1; i <= w - x2; ++i) { s += "R"; } s += "D"; for(int i = 1; i <= w - x2; ++i) { s += "L"; } return s; } if(h == 3) { if(y1 == 3) { return upsidedown(solve(h, w, x1, h+1-y1, x2, h+1-y2)); } if(x2 < x1) { return mirror(solve(h, w, w+1-x1, y1, w+1-x2, y2)); } if(x2 == x1) { if(y2 == 2) { //y1 = 1 if(x1%2 == 1) { return mirror(solve(h, w, w+1-x1, y1, w+1-x2, y2)); } string s = ""; for(int i = 1; i < x1; ++i) { s += "L"; } s += "UU"; for(int i = 1; i < x1/2; ++i) { s += "RDRU"; } s += "R"; if(w == x1) { s += "D"; return s; } for(int i = 1; i <= w - x1; ++i) { s += "R"; } s += "DD"; for(int i = 1; i <= (w - x1 - 1)/2; ++i) { s += "LULD"; } s += "LUL"; return s; } if(y1 == 2) { return reverse(solve(h, w, x2, y2, x1, y1)); } //y1 = 1 and y2 = 3 if(x1%2 == 0) return ""; string s = ""; for(int i = 1; i <= x1 - 1; ++i) { s += "L"; } s += "U"; for(int i = 1; i <= x1/2; ++i) { s += "URDR"; } for(int i = 1; i <= (w - x1)/2; ++i) { s += "RDRU"; } s += "U"; for(int i = 1; i <= (w - x1); ++i) { s += "L"; } return s; } if(w%2 == 0) { if((x1 + y1)%2 == 1) { if(x2 > x1 + 1) { return ""; } if(y1 == 2) { return ""; } //x2 = x1 + 1, y1 = 1 //x1%2 = 0 if(y2 == 1) { string s = ""; for(int i = 1; i < x1; ++i) { s += "L"; } s += "UU"; for(int i = 1; i <= x1/2; ++i) { s += "RDRU"; } for(int i = 1; i <= w - x2; ++i) { s += "R"; } s += "DD"; for(int i = 1; i <= (w - x2)/2; ++i) { s += "LULD"; } s += "L"; return s; } if(y2 == 2) { return ""; } if(y2 == 3) { string s = ""; for(int i = 1; i < x1; ++i) { s += "L"; } s += "UU"; for(int i = 1; i < x2/2; ++i) { s += "RDRU"; } s += "RDRD"; for(int i = 1; i <= w - x2; ++i) { s += "R"; } s += "UU"; for(int i = 1; i <= (w - x2)/2; ++i) { s += "LDLU"; } s += "L"; return s; } } else { if(y1 == 1) { if(y2 == 1) { string s = ""; for(int i = 1; i < x1; ++i) { s += "L"; } s += "UU"; for(int i = 1; i <= x1/2; ++i) { s += "RDRU"; } for(int i = 1; i <= (x2 - x1)/2; ++i) { s += "RDDRUU"; } s += "RD"; for(int i = 1; i <= (w - x2)/2; ++i) { s += "RURD"; } s += "D"; for(int i = 1; i <= w - x2; ++i) { s += "L"; } return s; } if(y2 == 2) { string s = ""; for(int i = 1; i < x1; ++i) { s += "L"; } s += "UU"; for(int i = 1; i <= x1/2; ++i) { s += "RDRU"; } for(int i = 1; i < (x2 - x1)/2; ++i) { s += "RDDRUU"; } s += "RDDR"; for(int i = 1; i <= w - x2; ++i) { s += "R"; } s += "UU"; for(int i = 1; i <= (w - x2)/2; ++i) { s += "LDLU"; } s += "LD"; return s; } string s = ""; for(int i = w - x1; i >= 1; --i) { s += "R"; } s += "U"; for(int i = 1; i <= (w - x2)/2; ++i) { s += "ULDL"; } for(int i = 1; i <= x2 - x1; ++i) { s += "L"; } for(int i = 1; i <= x1/2; ++i) { s += "LDLU"; } s += "U"; for(int i = 1; i < x2; ++i) { s += "R"; } return s; } else { //w is even //x1 + y1 is even //y1 is 2 if(y2 == 3) { return upsidedown(solve(h, w, x1, h+1-y1, x2, h+1-y2)); } if(y2 == 1) { return reverse(solve(h, w, x2, y2, x1, y1)); } //y2 = 2 string s = ""; s += "U"; for(int i = 1; i < x1/2; ++i) { s += "LDLU"; } s += "LDD"; for(int i = 1; i < x1; ++i) { s += "R"; } for(int i = 1; i <= (x2 - x1)/2; ++i) { s += "RUURDD"; } s += "R"; for(int i = 1; i <= (w - x2)/2; ++i) { s += "RURD"; } s += "RUU"; for(int i = 1; i <= w - x2; ++i) { s += "L"; } s += "D"; return s; } } } else { //w is odd if(y1 == 1 && y2 == 1) { //x1 and x2 are odd string s = ""; for(int i = 1; i < x1; ++i) { s += "L"; } s += "UU"; for(int i = 1; i <= x1/2; ++i) { s += "RDRU"; } for(int i = 1; i <= w - x1; ++i) { s += "R"; } s += "D"; for(int i = 1; i <= (w - x2)/2; ++i) { s += "DLUL"; } for(int i = 1; i < x2 - x1; ++i) { s += "L"; } s += "D"; for(int i = 1; i < x2 - x1; ++i) { s += "R"; } return s; } if(y1 == 1 && y2 == 2) { string s = ""; for(int i = 1; i < x1; ++i) { s += "L"; } s += "UU"; for(int i = 1; i <= x1/2; ++i) { s += "RDRU"; } for(int i = 1; i <= (x2 - x1)/2; ++i) { s += "RDDRUU"; } for(int i = 1; i <= w - x2 + 1; ++i) { s += "R"; } s += "D"; for(int i = 1; i <= (w - x2)/2; ++i) { s += "DLUL"; } s += "DLU"; return s; } if(y1 == 1 && y2 == 3) { string s = ""; for(int i = 1; i < x1; ++i) { s += "L"; } s += "UU"; for(int i = 1; i <= x1/2; ++i) { s += "RDRU"; } for(int i = 1; i < (x2 - x1)/2; ++i) { s += "RDDRUU"; } s += "RDD"; for(int i = 1; i <= w - x2 + 1; ++i) { s += "R"; } s += "UU"; for(int i = 1; i <= (w - x2)/2; ++i) { s += "LDLU"; } return s; } if(y1 == 2 && y2 == 2) { string s = "D"; for(int i = 1; i < x1; ++i) { s += "L"; } s += "U"; for(int i = 1; i < x1/2; ++i) { s += "URDR"; } s += "UR"; for(int i = 1; i < (x2 - x1)/2; ++i) { s += "RDDRUU"; } s += "RDDR"; for(int i = 1; i <= w - x2; ++i) { s += "R"; } s += "U"; for(int i = 1; i <= (w - x2)/2; ++i) { s += "ULDL"; } s += "ULD"; return s; } if(y2 == 3) { return upsidedown(solve(h, w, x1, h+1-y1, x2, h+1-y2)); } return reverse(solve(h, w, x2, y2, x1, y1)); } } //h >= 4 //also w >= 4 if(x2 < x1) { return reverse(solve(h, w, x2, y2, x1, y1)); } if(x1 >= 3) { string s = solve(h, w-2, x1-2, y1, x2-2, y2); int x = x1 - 2; int y = y1; string t = ""; bool f = true; for(int i = 0; i < s.size(); ++i) { if(x == 1 && s[i] != 'R' && f) { t += 'L'; if(s[i] == 'U') { t += solve(h, 2, 2, y, 2, y+1); } else { t += solve(h, 2, 2, y, 2, y-1); } t += 'R'; f = false; continue; } else { t += s[i]; if(s[i] == 'U') { ++y; } if(s[i] == 'D') { --y; } if(s[i] == 'L') { --x; } if(s[i] == 'R') { ++x; } } } return t; } if(x2 <= w - 2) { string s = solve(h, w-2, x1, y1, x2, y2); int x = x1; int y = y1; string t = ""; bool f = true; for(int i = 0; i < s.size(); ++i) { if(x == w - 2 && s[i] != 'L' && f) { t += 'R'; if(s[i] == 'U') { t += solve(h, 2, 1, y, 1, y+1); } else { t += solve(h, 2, 1, y, 1, y-1); } t += 'L'; f = false; continue; } else { t += s[i]; if(s[i] == 'U') { ++y; } if(s[i] == 'D') { --y; } if(s[i] == 'L') { --x; } if(s[i] == 'R') { ++x; } } } return t; } //x1 = 1 or 2, x2 = w or w-1 int a = -1; string A = ""; for(int i = 1; i <= h; ++i) { A = solve(h, 2, x1, y1, 2, i); if(A.size() != 0) { a = i; break; } } A += "R"; A += solve(h, w-2, 1, a, x2-2, y2); return A; } int main() { int t; cin >> t; while(t > 0) { --t; int h, w, x1, y1, x2, y2; cin >> h >> w >> y1 >> x1 >> y2 >> x2; y1 = h+1 - y1; y2 = h+1 - y2; string s = solve(h, w, x1, y1, x2, y2); if(s.size() == 0) { cout << "NO\n"; } else { cout << "YES\n"; cout << s << "\n"; } } }
Test details
Test 1
Group: 1, 5
Verdict: WRONG ANSWER
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 RRRRRRRUULDLULDLULDLLUR ... 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 ULLLLDRDRURDRRUURDDRUURDDRUURD... 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 RRDDDDLLLUURDRUULLULLLLLLUUUUL... 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 LDRDLDRRUUUULLLDDDDLUUUULDDDDD... 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 RRRDDLLLURR NO YES URRRDDLULDL ... 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 RRRRUULDLULLDR 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 URDRURDDLLLLUULDDLUULDD ... 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 RRDDLULDLUUURRR YES RRRUUULLLDDRRUL 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 DLULDLUURRRRDDDLLLLDRRRRDLLLLL... 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 RRRRRRRUULDLULDLULDLULDLDLLLUU... 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 |