Task: | Ruudukko |
Sender: | Olli |
Submission time: | 2020-11-07 22:13:48 +0200 |
Language: | C++ (C++11) |
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.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 secondconst 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 || h == 1) {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 = 1if(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 = 1if((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 = 1if(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 = 3if(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 = 0if(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 2if(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 = 2string 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 oddif(y1 == 1 && y2 == 1) {//x1 and x2 are oddstring 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 >= 4if(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-1int 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: 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 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 |