Task: | Ruudukko |
Sender: | Mahtimursu |
Submission time: | 2023-04-05 18:08:52 +0300 |
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.00 s | 1, 5 | details |
#2 | ACCEPTED | 0.00 s | 2, 5 | details |
#3 | ACCEPTED | 0.00 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.00 s | 2, 5 | details |
#8 | ACCEPTED | 0.00 s | 2, 5 | details |
#9 | ACCEPTED | 0.00 s | 3, 5 | details |
#10 | ACCEPTED | 0.00 s | 3, 5 | details |
#11 | ACCEPTED | 0.00 s | 3, 5 | details |
#12 | ACCEPTED | 0.00 s | 3, 5 | details |
#13 | ACCEPTED | 0.00 s | 4, 5 | details |
#14 | ACCEPTED | 0.10 s | 5 | details |
#15 | ACCEPTED | 0.01 s | 3, 5 | details |
#16 | ACCEPTED | 0.02 s | 5 | details |
Compiler report
input/code.cpp: In function 'std::string solve_mid(int, int, int, int)': input/code.cpp:349:1: warning: no return statement in function returning non-void [-Wreturn-type] 349 | } | ^
Code
#include <bits/stdc++.h> typedef long long ll; #define M 1000000007 #define N (1 << 18) #define y first #define x second using namespace std; namespace mango { string rev(string str) { for (auto& c : str) { if (c == 'L') c = 'R'; else if (c == 'R') c = 'L'; else if (c == 'D') c = 'U'; else c = 'D'; } reverse(str.begin(), str.end()); return str; } string fix(string str) { for (auto& c : str) { if (c == 'U') c = 'D'; else if (c == 'D') c = 'U'; } return str; } string solveSmall(int h, int w, int y0, int x0, int y1, int x1) { if (x0 > x1 || (x0 == x1 && y0 > y1)) return rev(solveSmall(h, w, y1, x1, y0, x0)); if (h == 1) { if (x0 == 0 && x1 == w-1) return string(w-1, 'R'); if (x0 == w-1 && x1 == 0) return string(w-1, 'L'); return ""; } else { if (x0 == x1 && 0 < x0 && x0 < w-1) return ""; string res; if (x0 == x1 && x0 == 0) { for (int i = 0; i < w-1; ++i) res.push_back('R'); if (y0 == 0) res.push_back('U'); else res.push_back('D'); for (int i = 0; i < w-1; ++i) res.push_back('L'); } else { for (int i = 0; i < x0; ++i) res.push_back('L'); if (y0 == 0) res.push_back('U'); else res.push_back('D'); for (int i = 0; i < x0; ++i) res.push_back('R'); if (x0 == x1) return res; for (int i = 0; i < x1 - x0 - 1; ++i) { res.push_back('R'); if ((i ^ y0) & 1) res.push_back('U'); else res.push_back('D'); } res.push_back('R'); for (int i = 0; i < w-1 - x1; ++i) res.push_back('R'); if (y1 == 0) res.push_back('D'); else res.push_back('U'); for (int i = 0; i < w-1 - x1; ++i) res.push_back('L'); } return res; } } string solve2(int n, int m, pair<int, int> s, pair<int, int> t) { return fix(solveSmall(n, m, s.y - 1, s.x - 1, t.y - 1, t.x - 1)); } }; bool check_small(int h, int w, int y0, int x0, int y1, int x1) { if (x0 > x1 || (x0 == x1 && y0 > y1)) return check_small(h, w, y1, x1, y0, x0); if (h == 1) { if (x0 == 0 && x1 == w-1) return true; if (x0 == w-1 && x1 == 0) return true; return false; } else { if (x0 == x1 && 0 < x0 && x0 < w-1) return false; return true; } } bool works(int h, int w, int y0, int x0, int y1, int x1) { if (y0 == y1 && x0 == x1) return false; if (w < h) return works(w, h, x0, y0, x1, y1); if (! ((h*w ^ abs(x0 - x1) ^ abs(y0 - y1)) & 1)) return false; if ((h*w & 1) && ((x0 + y0) & 1)) return false; if (h <= 2) return check_small(h, w, y0, x0, y1, x1); if (h == 3 && (!(w & 1))) { if (y0 == 1) { if ((x0 & 1) && x1 < x0) return false; if (!(x0 & 1) && x1 > x0) return false; } else { if (!(x0 & 1) && (x1 < x0 - 1)) return false; if ((x0 & 1) && (x1 > x0 + 1)) return false; } } return true; } bool inside(int n, int m, pair<int, int> p) { return p.x <= m && p.y <= n && p.x > 0 && p.y > 0; } bool ok(int h, int w, pair<int, int> s, pair<int, int> t) { if (h == 0) return s.x == t.x; return works(h, w, s.y - 1, s.x - 1, t.y - 1, t.x - 1); } pair<int, int> offset(pair<int, int> p, pair<int, int> off) { return {p.y + off.y, p.x + off.x}; } const int cutoff = 20; string rev(string s) { map<char, char> sw; sw['U'] = 'D'; sw['D'] = 'U'; sw['L'] = 'R'; sw['R'] = 'L'; string ans; for (char c : s) ans += sw[c]; reverse(ans.begin(), ans.end()); return ans; } bool vis[51][51]; string run_brute(int n, int m, pair<int, int> c, pair<int, int> t, int left) { if (c.x < 1 || c.x > m || c.y < 1 || c.y > n) return "X"; if (vis[c.y][c.x]) return "X"; if (left == 0) { return c == t ? "" : "X"; } vis[c.y][c.x] = 1; string p = run_brute(n, m, {c.y - 1, c.x}, t, left - 1); if (p != "X") return "U" + p; p = run_brute(n, m, {c.y + 1, c.x}, t, left - 1); if (p != "X") return "D" + p; p = run_brute(n, m, {c.y, c.x - 1}, t, left - 1); if (p != "X") return "L" + p; p = run_brute(n, m, {c.y, c.x + 1}, t, left - 1); if (p != "X") return "R" + p; vis[c.y][c.x] = 0; return "X"; } string brute(int n, int m, pair<int, int> s, pair<int, int> t) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) vis[i][j] = 0; } return run_brute(n, m, s, t, n * m - 1); } string c2(int n, int m, pair<int, int> s, pair<int, int> t, int times) { pair<int, int> dif = {s.y - t.y, s.x - t.x}; string ans_first; string ans_second; string ans_second_mid; if (dif == make_pair(0, -1)) { ans_first += string(s.x - 1, 'L'); ans_first += s.y == 2 ? "U" : "D"; ans_first += string(s.x - 1, 'R'); ans_first += s.y == 2 ? "U" : "D"; ans_second += string(m - s.x, 'R'); ans_second += s.y == 2 ? "D" : "U"; ans_second_mid = s.y == 2 ? "D" : "U"; ans_second += string(m - t.x, 'L'); } if (dif == make_pair(0, 1)) { ans_first += string(m - s.x, 'R'); ans_first += s.y == 2 ? "U" : "D"; ans_first += string(m - s.x, 'L'); ans_first += s.y == 2 ? "U" : "D"; ans_second += string(s.x - 1, 'L'); ans_second += s.y == 2 ? "D" : "U"; ans_second_mid = s.y == 2 ? "D" : "U"; ans_second += string(t.x - 1, 'R'); } if (dif == make_pair(-1, 0)) { ans_first += string(s.y - 1, 'U'); ans_first += s.x == 2 ? "L" : "R"; ans_first += string(s.y - 1, 'D'); ans_first += s.x == 2 ? "L" : "R"; ans_second += string(n - s.y, 'D'); ans_second += s.x == 2 ? "R" : "L"; ans_second_mid = s.x == 2 ? "R" : "L"; ans_second += string(n - t.y, 'U'); } if (dif == make_pair(1, 0)) { ans_first += string(n - s.y, 'D'); ans_first += s.x == 2 ? "L" : "R"; ans_first += string(n - s.y, 'U'); ans_first += s.x == 2 ? "L" : "R"; ans_second += string(s.y - 1, 'U'); ans_second += s.x == 2 ? "R" : "L"; ans_second_mid = s.x == 2 ? "R" : "L"; ans_second += string(t.y - 1, 'D'); } string ans; for (int i = 0; i < times; ++i) ans += ans_first; ans.pop_back(); for (int i = 0; i < times; ++i) { ans += ans_second; if (i != times - 1) ans += ans_second_mid; } return ans; } string solve_strip(tuple<int, int, pair<int, int>, pair<int, int>> p1, string path, pair<int, int> pos, int times) { map<char, pair<int, int>> dir_to_dif; dir_to_dif['U'] = {-1, 0}; dir_to_dif['D'] = {1, 0}; dir_to_dif['R'] = {0, 1}; dir_to_dif['L'] = {0, -1}; string res; pair<int, int> tgt = get<2>(p1); if (pos.x == tgt.x || pos.y == tgt.y) { bool begin = 0; if (get<3>(p1).y == 1 && path[0] == 'D') { begin = 1; } else if (get<3>(p1).y > 1 && path[0] == 'U') { begin = 1; } else if (get<3>(p1).x == 1 && path[0] == 'R') { begin = 1; } else if (get<3>(p1).x > 1 && path[0] == 'L') { begin = 1; } if (begin) { pair<int, int> dif = dir_to_dif[path[res.size()]]; pos = make_pair(pos.y + dif.y, pos.x + dif.x); res += (path[res.size()]); } } while (pos.x != tgt.x && pos.y != tgt.y) { pair<int, int> dif = dir_to_dif[path[res.size()]]; pos = make_pair(pos.y + dif.y, pos.x + dif.x); res += (path[res.size()]); } string end_path = path.size() > res.size() + 1 ? path.substr(res.size() + 1, 1e5) : ""; if (get<3>(p1).y == 1) { res = res + "U" + c2(2, get<1>(p1), {2, pos.x}, {2, pos.x + dir_to_dif[path[res.size()]].x}, times) + "D"; } else if (get<3>(p1).y > 1) { res = res + "D" + c2(2, get<1>(p1), {1, pos.x}, {1, pos.x + dir_to_dif[path[res.size()]].x}, times) + "U"; } else if (get<3>(p1).x == 1) { res = res + "L" + c2(get<0>(p1), 2, {pos.y, 2}, {pos.y + dir_to_dif[path[res.size()]].y, 2}, times) + "R"; } else if (get<3>(p1).x > 1) { res = res + "R" + c2(get<0>(p1), 2, {pos.y, 1}, {pos.y + dir_to_dif[path[res.size()]].y, 1}, times) + "L"; } return res + end_path; } string solve_m(int n, int m, pair<int, int> s, pair<int, int> t) { if (s.x > t.x) return rev(solve_m(n, m, t, s)); int min_j = min(s.x, t.x); int max_j = max(s.x, t.x); if (min_j > 2) { if (ok(n, m - 2, offset(s, {0, -2}), offset(t, {0, -2}))) { auto x1 = make_tuple(n, 2, make_pair(0, 1), make_pair(0,1)); string path = solve_m(n, m - 2, offset(s, {0, -2}), offset(t, {0, -2})); return solve_strip(x1, path, offset(s, {0, -2}), 1); } } if (max_j < m - 1) { if (ok(n, m - 2, s, t)) { auto x1 = make_tuple(n, 2, make_pair(0, m - 2), make_pair(0,2)); string path = solve_m(n, m - 2, s, t); return solve_strip(x1, path, s, 1); } } set<int> st_i; st_i.insert(1); st_i.insert(2); if (n % 2 == 0) st_i.insert(n); else st_i.insert(n - 1); for (int i : st_i) { int first_m = 2; int second_m = m - 2; pair<int, int> first_e = {i, first_m}; pair<int, int> second_e = {i, first_m + 1}; if (inside(n, first_m, s) && inside(n, second_m, offset(t, {0, -first_m})) && ok(n, first_m, s, first_e) && ok(n, second_m, offset(t, {0, -first_m}), offset(second_e, {0, -first_m})) ) { string s1 = solve_m(n, first_m, s, first_e); string s2 = solve_m(n, second_m, offset(second_e, {0, -first_m}), offset(t, {0, -first_m})); return s1 + "R" + s2; } } return brute(n, m, s, t); } string solve_mid(int n, int m, int j1, int j2) { } string solve(int n, int m, pair<int, int> s, pair<int, int> t) { int min_i = min(s.y, t.y); int max_i = max(s.y, t.y); for (int i = 2 /*min_i - min_i % 2*/; i > 0; i -= 2) { if (min_i > i) { if (ok(n - i, m, offset(s, {-i, 0}), offset(t, {-i, 0}))) { auto x1 = make_tuple(2, m, make_pair(1, 0), make_pair(1,0)); string path = solve(n - 2, m, offset(s, {-2, 0}), offset(t, {-2, 0})); return solve_strip(x1, path, offset(s, {-2, 0}), i / 2); } } } if (max_i < n - 1) { if (ok(n - 2, m, s, t)) { auto x1 = make_tuple(2, m, make_pair(n - 2, 0), make_pair(2,0)); string path = solve(n - 2, m, s, t); return solve_strip(x1, path, s, 1); } } if (n <= 3 || max_i <= 2 || min_i > 2) { return solve_m(n, m, s, t); } // Assume s.y <= 2 and t.y >= n - 1 int left_n = 2; int right_n = 2 + (n % 2); int mid = n - left_n - right_n; for (int j1 = 1; j1 <= m; ++j1) { for (int j2 = 1; j2 <= m; ++j2) { pair<int, int> first_e = {left_n, j1}; pair<int, int> second_e = {1, j2}; if (ok(left_n, m, s, first_e) && ok(right_n, m, second_e, offset(t, {-(left_n + mid), 0})) && ok(mid, m, {1, j1}, {mid, j2})) { string ans = mango::solve2(left_n, m, s, first_e); //if (mid != 0) ans += "D" + solve_mid(mid, m, j1, j2); if (mid != 0) ans += "D" + solve(mid, m, {1, j1}, {mid, j2}); ans += "D" + solve_m(right_n, m, second_e, offset(t, {-(left_n + mid), 0})); return ans; } } } return solve_m(n, m, s, t); } void test_case() { int n, m; pair<int, int> s, t; cin >> n >> m >> s.y >> s.x >> t.y >> t.x; if (!ok(n, m, s, t)) { cout << "NO" << endl; return; } cout << "YES" << endl; //cout << n << " " << m << " " << s.y << " " << s.x << " " << t.y << " " << t.x << endl; string ans = s <= t ? solve(n, m, s, t) : rev(solve(n, m, t, s)); cout << ans << "\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; cin >> t; for (int i = 0; i < t; ++i) { test_case(); } return 0; } /* */ /* */
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 RRRRRRULLLLLLLDLULDLULDLULDLUL... 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 ULLLLLLLLLLUUUUUUUUUUUUUUUUURR... 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 RRRUUUUUUUUUUUUUUUUULLLLLLLLLL... 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 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 UURRRRDDLULDLU 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 LURRDDLLDRRRUUU YES RRRULLLUURRRDLL 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 RRRRRULLLLLLDLULDLULDLULDLULDL... 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 DRRRRRRRRRRRRRRRRRRRRRRRRRRRRR... Truncated |