| Task: | Ruudukko |
| Sender: | Mahtimursu |
| Submission time: | 2023-05-30 00:34:00 +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.00 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.01 s | 5 | details |
| #15 | ACCEPTED | 0.00 s | 3, 5 | details |
| #16 | ACCEPTED | 0.01 s | 5 | details |
Compiler report
input/code.cpp: In function 'void solver_all::solve_mid_rev(int, int, int, int, std::pair<int, int>)':
input/code.cpp:631:9: warning: unused variable 'on' [-Wunused-variable]
631 | int on = n;
| ^~
input/code.cpp: In function 'void solve_mid_rev(int, int, int, int, std::pair<int, int>)':
input/code.cpp:1397:9: warning: unused variable 'on' [-Wunused-variable]
1397 | int on = n;
| ^~
input/code.cpp: In function 'void solver_all::solve_strip_hor(bool, int, int, std::pair<int, int>)':
input/code.cpp:367:5: warning: 'up' may be used uninitialized [-Wmaybe-uninitialized]
367 | if (up) {
| ^~
input/code.cpp: In function 'void solver_all::solve_strip_ver(bool, int, int, std::pair<int, int>)':
input/code.cpp:470:5: warning: 'left' may be used uninitialized [-Wmaybe-uninitialized]
470 | if (left) {
| ^~
input/code.cpp: In function 'void solve_strip_hor(bool, int, int, std::pair<int, int>)':
input/code.cpp:1133:5: warning: 'u...Code
#include <bits/stdc++.h>
typedef long long ll;
#define y first
#define x second
using namespace std;
namespace solver_all {
int s2 = 0;
const int MAX_N = 10000;
char result[MAX_N + 1][MAX_N + 1];
inline void st(char c, pair<int, int> pos, pair<int, int> offset) {
result[pos.y + offset.y][pos.x + offset.x] = c;
}
inline char gt(pair<int, int> pos, pair<int, int> offset) {
return result[pos.y + offset.y][pos.x + offset.x];
}
inline pair<int, int> step(char c, pair<int, int> pos) {
if (c == 'U') return {pos.y - 1, pos.x};
if (c == 'D') return {pos.y + 1, pos.x};
if (c == 'R') return {pos.y, pos.x + 1};
if (c == 'L') return {pos.y, pos.x - 1};
return {0, 0};
}
inline char gt_rev(char c) {
if (c == 'U') return 'D';
if (c == 'D') return 'U';
if (c == 'R') return 'L';
if (c == 'L') return 'R';
return '?';
}
void rev_from(pair<int, int> s, pair<int, int> t, pair<int, int> offset) {
// s = start in the wrong order
// means that pos[t] will be empty
// but pos[s] should be empty
char c = gt(s, offset);
s = step(gt(s, offset), s);
while (s != t) {
char nxt = gt(s, offset);
st(gt_rev(c), s, offset);
c = nxt;
s = step(nxt, s);
}
st(gt_rev(c), s, offset);
}
namespace mango {
void solveSmall(int h, int w, int y0, int x0, int y1, int x1, pair<int, int> offset) {
bool swp = 0;
if (x0 > x1 || (x0 == x1 && y0 > y1)) {
swp = 1;
swap(x0, x1);
swap(y0, y1);
}
if (h == 1) {
if (x0 == 1 && x1 == w) {
for (int i = 0; i < w - 1; ++i) {
if (!swp) {
st('R', {y0, x0}, offset);
offset.x++;
} else {
offset.x++;
st('L', {y0, x0}, offset);
}
}
return;
}
if (x0 == w && x1 == 1) {
for (int i = 0; i < w - 1; ++i) {
if (!swp) {
st('L', {y0, x0}, offset);
offset.x--;
} else {
offset.x--;
st('R', {y0, x0}, offset);
}
}
return;
}
} else {
string res;
if (x0 == x1 && x0 == 1) {
for (int i = 0; i < w-1; ++i) {
if (!swp)
st('R', {y0, x0}, offset);
offset.x++;
if (swp)
st('L', {y0, x0}, offset);
}
if (y0 == 1) {
if (!swp)
st('D', {y0, x0}, offset);
offset.y++;
if (swp)
st('U', {y0, x0}, offset);
}
else {
if (!swp)
st('U', {y0, x0}, offset);
offset.y--;
if (swp)
st('D', {y0, x0}, offset);
}
for (int i = 0; i < w-1; ++i) {
if (!swp)
st('L', {y0, x0}, offset);
offset.x--;
if (swp)
st('R', {y0, x0}, offset);
}
} else {
for (int i = 1; i < x0; ++i) {
if (!swp)
st('L', {y0, x0}, offset);
offset.x--;
if (swp)
st('R', {y0, x0}, offset);
}
if (y0 == 1) {
if (!swp)
st('D', {y0, x0}, offset);
offset.y++;
if (swp)
st('U', {y0, x0}, offset);
}
else {
if (!swp)
st('U', {y0, x0}, offset);
offset.y--;
if (swp)
st('D', {y0, x0}, offset);
}
for (int i = 1; i < x0; ++i) {
if (!swp)
st('R', {y0, x0}, offset);
offset.x++;
if (swp)
st('L', {y0, x0}, offset);
}
if (x0 == x1) return;
for (int i = 1; i < x1 - x0; ++i) {
if (!swp)
st('R', {y0, x0}, offset);
offset.x++;
if (swp)
st('L', {y0, x0}, offset);
if (((i - 1) ^ (y0 - 1)) & 1) {
if (!swp)
st('D', {y0, x0}, offset);
offset.y++;
if (swp)
st('U', {y0, x0}, offset);
}
else {
if (!swp)
st('U', {y0, x0}, offset);
offset.y--;
if (swp)
st('D', {y0, x0}, offset);
}
}
if (!swp)
st('R', {y0, x0}, offset);
offset.x++;
if (swp)
st('L', {y0, x0}, offset);
for (int i = 0; i < w - x1; ++i) {
if (!swp)
st('R', {y0, x0}, offset);
offset.x++;
if (swp)
st('L', {y0, x0}, offset);
}
if (y1 == 1) {
if (!swp)
st('U', {y0, x0}, offset);
offset.y--;
if (swp)
st('D', {y0, x0}, offset);
}
else {
if (!swp)
st('D', {y0, x0}, offset);
offset.y++;
if (swp)
st('U', {y0, x0}, offset);
}
for (int i = 0; i < w - x1; ++i) {
if (!swp)
st('L', {y0, x0}, offset);
offset.x--;
if (swp)
st('R', {y0, x0}, offset);
}
}
}
}
void solve2(int n, int m, pair<int, int> s, pair<int, int> t, pair<int, int> offset) {
s2++;
solveSmall(n, m, s.y, s.x, t.y, t.x, offset);
}
};
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;
if (!inside(h, w, s) || !inside(h, w, t)) return false;
return works(h, w, s.y - 1, s.x - 1, t.y - 1, t.x - 1);
}
pair<int, int> ot(pair<int, int> p, pair<int, int> off) {
return {p.y + off.y, p.x + off.x};
}
const int cutoff = 20;
bool vis[MAX_N + 1][MAX_N + 1];
bool run_brute(int n, int m, pair<int, int> c, pair<int, int> t, int left, pair<int, int> offset) {
if (c.x < 1 || c.x > m || c.y < 1 || c.y > n) return false;
if (vis[c.y][c.x]) return false;
if (left == 0) {
if (c != t) return false;
st('E', c, offset);
return true;
}
vis[c.y][c.x] = 1;
if (run_brute(n, m, {c.y - 1, c.x}, t, left - 1, offset)) {
st('U', c, offset);
return true;
}
if (run_brute(n, m, {c.y + 1, c.x}, t, left - 1, offset)) {
st('D', c, offset);
return true;
}
if (run_brute(n, m, {c.y, c.x - 1}, t, left - 1, offset)) {
st('L', c, offset);
return true;
}
if (run_brute(n, m, {c.y, c.x + 1}, t, left - 1, offset)) {
st('R', c, offset);
return true;
}
vis[c.y][c.x] = 0;
return false;
}
int c = 0;
void brute(int n, int m, pair<int, int> s, pair<int, int> t, pair<int, int> offset) {
c++;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) vis[i][j] = 0;
}
run_brute(n, m, s, t, n * m - 1, offset);
}
void solve_strip_hor(bool left, int n, int m, pair<int, int> offset) {
int s_idx = 0;
bool up;
pair<int, int> cp;
// cout << "here hor " << left << " " << n << " " << m << " " << offset.y << " " << offset.x << endl;
if (left) {
for (int i = 1; i <= n; ++i) {
char c = gt({i, m + 1}, offset);
if (c == 'D') {
up = 1;
s_idx = i;
break;
} else if (c == 'U') {
up = 0;
s_idx = i;
break;
}
}
st('L', {s_idx, m + 1}, offset);
cp = {s_idx, m};
} else {
for (int i = 1; i <= n; ++i) {
char c = gt({i, 0}, offset);
if (c == 'D') {
up = 1;
s_idx = i;
break;
} else if (c == 'U') {
up = 0;
s_idx = i;
break;
}
}
st('R', {s_idx, 0}, offset);
cp = {s_idx, 1};
}
if (up) {
while (cp.y != 1) {
st('U', cp, offset);
cp.y--;
}
} else {
while (cp.y != n) {
st('D', cp, offset);
cp.y++;
}
}
if (left) {
st('L', cp, offset);
cp.x--;
} else {
st('R', cp, offset);
cp.x++;
}
if (up) {
while (cp.y != n) {
st('D', cp, offset);
cp.y++;
}
} else {
while (cp.y != 1) {
st('U', cp, offset);
cp.y--;
}
}
if (left) {
st('R', cp, offset);
cp.x++;
} else {
st('L', cp, offset);
cp.x--;
}
if (up) {
while (cp.y != s_idx + 1) {
st('U', cp, offset);
cp.y--;
}
} else {
while (cp.y != s_idx - 1) {
st('D', cp, offset);
cp.y++;
}
}
if (left) {
st('R', cp, offset);
cp.x++;
} else {
st('L', cp, offset);
cp.x--;
}
}
void solve_strip_ver(bool up, int n, int m, pair<int, int> offset) {
int s_idx = 0;
bool left;
pair<int, int> cp;
// cout << "here hor " << left << " " << n << " " << m << " " << offset.y << " " << offset.x << endl;
if (up) {
for (int i = 1; i <= m; ++i) {
char c = gt({n + 1, i}, offset);
if (c == 'R') {
left = 1;
s_idx = i;
break;
} else if (c == 'L') {
left = 0;
s_idx = i;
break;
}
}
st('U', {n + 1, s_idx}, offset);
cp = {n, s_idx};
} else {
for (int i = 1; i <= m; ++i) {
char c = gt({0, i}, offset);
if (c == 'R') {
left = 1;
s_idx = i;
break;
} else if (c == 'L') {
left = 0;
s_idx = i;
break;
}
}
st('D', {0, s_idx}, offset);
cp = {1, s_idx};
}
if (left) {
while (cp.x != 1) {
st('L', cp, offset);
cp.x--;
}
} else {
while (cp.x != m) {
st('R', cp, offset);
cp.x++;
}
}
if (up) {
st('U', cp, offset);
cp.y--;
} else {
st('D', cp, offset);
cp.y++;
}
if (left) {
while (cp.x != m) {
st('R', cp, offset);
cp.x++;
}
} else {
while (cp.x != 1) {
st('L', cp, offset);
cp.x--;
}
}
if (up) {
st('D', cp, offset);
cp.y++;
} else {
st('U', cp, offset);
cp.y--;
}
if (left) {
while (cp.x != s_idx + 1) {
st('L', cp, offset);
cp.x--;
}
} else {
while (cp.x != s_idx - 1) {
st('R', cp, offset);
cp.x++;
}
}
if (up) {
st('D', cp, offset);
cp.y++;
} else {
st('U', cp, offset);
cp.y--;
}
}
void solve_m(int n, int m, pair<int, int> s, pair<int, int> t, pair<int, int> offset) {
// cout << "here: " << n << " " << m << " " << s.y << " " << s.x << " " << t.y << " " << t.x << endl;
int min_j = min(s.x, t.x);
int max_j = max(s.x, t.x);
/*for (int j = min_j - min_j % 2; j > 0; j -= 2) {*/
for (int j = 2; j > 0; j -= 2) {
if (min_j > j) {
if (ok(n, m - j, ot(s, {0, -j}), ot(t, {0, -j}))) {
solve_m(n, m - j, ot(s, {0, -j}), ot(t, {0, -j}), ot(offset, {0, j}));
solve_strip_hor(true, n, j, offset);
return;
}
}
}
/*for (int j = (m - max_j) / 2 * 2; j > 0; j -= 2) {*/
for (int j = 2; j > 0; j -= 2) {
if (max_j <= m - j) {
if (ok(n, m - j, s, t)) {
solve_m(n, m - j, s, t, offset);
solve_strip_hor(false, n, j, ot(offset, {0, m - j}));
return;
}
}
}
if (s.x > t.x) {
// cout << "reversed: " << s.y << " " << s.x << " " << t.y << " " << t.x << endl;
char c = gt(t, offset);
solve_m(n, m, t, s, offset);
rev_from(t, s, offset);
st(c, t, offset);
return;
}
vector<int> st_i;
st_i.push_back(1);
st_i.push_back(2);
if (n % 2 == 0) st_i.push_back(n);
else st_i.push_back(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, ot(t, {0, -first_m}))
&& ok(n, first_m, s, first_e)
&& ok(n, second_m, ot(t, {0, -first_m}), ot(second_e, {0, -first_m}))
) {
solve_m(n, first_m, s, first_e, offset);
st('R', first_e, offset);
solve_m(n, second_m, ot(second_e, {0, -first_m}), ot(t, {0, -first_m}), ot(offset, {0, first_m}));
return;
}
}
brute(n, m, s, t, offset);
}
int ckmid = 0;
int ckmidloop = 0;
void solve_mid(int n, int m, int j1, int j2, pair<int, int> offset) {
while (n > 2) {
ckmidloop++;
if (n * m <= cutoff) {
brute(n, m, {1, j1}, {n, j2}, offset);
return;
}
for (int j = 2 - (j1 % 2); j <= m; j += 2) {
ckmid++;
if (j == j1 && j1 != 1 && j1 != m) continue;
if (ok(n - 2, m, {1, j}, {n - 2, j2})) {
mango::solve2(2, m, {1, j1}, {2, j}, offset);
offset.y += 2;
j1 = j;
break;
}
}
st('D', {0, j1}, offset);
n -= 2;
}
mango::solve2(2, m, {1, j1}, {2, j2}, offset);
}
void solve_mid_rev(int n, int m, int j1, int j2, pair<int, int> offset) {
// {n, j2} -> {1, j1}
//cout << "called: " << n << " " << m << " " << j1 << " " << j2 << " " << offset.y << " " << offset.x << endl;
int on = n;
while (n > 2) {
ckmidloop++;
if (n * m <= cutoff) {
brute(n, m, {n, j2}, {1, j1}, offset);
return;
}
for (int j = 2 - (j2 % 2); j <= m; j += 2) {
ckmid++;
if (j == j2 && j2 != 1 && j2 != m) continue;
if (ok(n - 2, m, {n - 2, j}, {1, j1})) {
mango::solve2(2, m, {2, j2}, {1, j}, ot(offset, {n - 2, 0}));
st('U', {1, j}, ot(offset, {n - 2, 0}));
j2 = j;
break;
}
}
n -= 2;
}
mango::solve2(2, m, {2, j2}, {1, j1}, offset);
/*for (int i = 1; i <= on + 1; ++i) {
for (int j = 1; j <= m; ++j) {
cout << gt({i, j}, offset);
}
cout << endl;
}
cout << "END\n";*/
}
int scc = 0;
int chc = 0;
void solve(int n, int m, pair<int, int> s, pair<int, int> t, pair<int, int> offset) {
scc++;
if (n <= 2) {
mango::solve2(n, m, s, t, offset);
return;
}
int min_i = min(s.y, t.y);
int max_i = max(s.y, t.y);
/*for (int i = min_i - min_i % 2; i > 0; i -= 2) {*/
for (int i = 2; i > 0; i -= 2) {
if (min_i > i) {
if (ok(n - i, m, ot(s, {-i, 0}), ot(t, {-i, 0}))) {
solve(n - i, m, ot(s, {-i, 0}), ot(t, {-i, 0}), ot(offset, {i, 0}));
solve_strip_ver(true, i, m, offset);
return;
}
}
}
/*for (int i = (n - max_i) / 2 * 2; i > 0; i -= 2) {*/
for (int i = 2; i > 0; i -= 2) {
if (max_i <= n - i) {
if (ok(n - i, m, s, t)) {
solve(n - i, m, s, t, offset);
solve_strip_ver(false, i, m, ot(offset, {n - i, 0}));
return;
}
}
}
if (n <= 3 || max_i <= 2 || min_i > 2) {
solve_m(n, m, s, t, offset);
return;
}
if (s > t) {
int left_n = 2;
int right_n = 2 + (n % 2);
int mid = n - left_n - right_n;
int color = (t.x + t.y) % 2;
for (int j1 = 1 + color; j1 <= m; j1 += 2) {
for (int j2 = 1 + color; j2 <= m; j2 += 2) {
chc++;
pair<int, int> first_e = {left_n, j1};
pair<int, int> second_e = {1, j2};
if (mid == 0 && j1 != j2) continue;
if (mid == 2 && j1 == j2 && j1 != 1 && j1 != m) continue;
if (ok(left_n, m, first_e, t)
&& ok(right_n, m, ot(s, {-(left_n + mid), 0}), second_e)
) {
solve_m(right_n, m, ot(s, {-(left_n + mid), 0}), second_e, ot(offset, {left_n + mid, 0}));
st('U', second_e, ot(offset, {left_n + mid, 0}));
if (mid != 0) {
solve_mid_rev(mid, m, j1, j2, ot(offset, {2, 0}));
st('U', {1, j1}, ot(offset, {2, 0}));
}
mango::solve2(left_n, m, first_e, t, offset);
return;
}
}
}
solve_m(n, m, s, t, offset);
return;
}
int left_n = 2;
int right_n = 2 + (n % 2);
int mid = n - left_n - right_n;
int color = (s.x + s.y) % 2;
for (int j1 = 1 + color; j1 <= m; j1 += 2) {
for (int j2 = 1 + color; j2 <= m; j2 += 2) {
chc++;
pair<int, int> first_e = {left_n, j1};
pair<int, int> second_e = {1, j2};
if (mid == 0 && j1 != j2) continue;
if (mid == 2 && j1 == j2 && j1 != 1 && j1 != m) continue;
if (ok(left_n, m, s, first_e)
&& ok(right_n, m, second_e, ot(t, {-(left_n + mid), 0}))
) {
mango::solve2(left_n, m, s, first_e, offset);
st('D', first_e, offset);
if (mid != 0) {
solve_mid(mid, m, j1, j2, ot(offset, {2, 0}));
st('D', {mid, j2}, ot(offset, {2, 0}));
}
solve_m(right_n, m, second_e, ot(t, {-(left_n + mid), 0}), ot(offset, {left_n + mid, 0}));
return;
}
}
}
solve_m(n, m, s, t, offset);
}
}
int s2 = 0;
const int MAX_N = 10000;
char result[MAX_N + 1][MAX_N + 1];
inline void st(char c, pair<int, int> pos, pair<int, int> offset) {
result[pos.y + offset.y][pos.x + offset.x] = c;
}
inline char gt(pair<int, int> pos, pair<int, int> offset) {
return result[pos.y + offset.y][pos.x + offset.x];
}
inline pair<int, int> step(char c, pair<int, int> pos) {
if (c == 'U') return {pos.y - 1, pos.x};
if (c == 'D') return {pos.y + 1, pos.x};
if (c == 'R') return {pos.y, pos.x + 1};
if (c == 'L') return {pos.y, pos.x - 1};
return {0, 0};
}
inline char gt_rev(char c) {
if (c == 'U') return 'D';
if (c == 'D') return 'U';
if (c == 'R') return 'L';
if (c == 'L') return 'R';
return '?';
}
void rev_from(pair<int, int> s, pair<int, int> t, pair<int, int> offset) {
// s = start in the wrong order
// means that pos[t] will be empty
// but pos[s] should be empty
char c = gt(s, offset);
s = step(gt(s, offset), s);
while (s != t) {
char nxt = gt(s, offset);
st(gt_rev(c), s, offset);
c = nxt;
s = step(nxt, s);
}
st(gt_rev(c), s, offset);
}
namespace mango {
void solveSmall(int h, int w, int y0, int x0, int y1, int x1, pair<int, int> offset) {
bool swp = 0;
if (x0 > x1 || (x0 == x1 && y0 > y1)) {
swp = 1;
swap(x0, x1);
swap(y0, y1);
}
if (h == 1) {
if (x0 == 1 && x1 == w) {
for (int i = 0; i < w - 1; ++i) {
if (!swp) {
st('R', {y0, x0}, offset);
offset.x++;
} else {
offset.x++;
st('L', {y0, x0}, offset);
}
}
return;
}
if (x0 == w && x1 == 1) {
for (int i = 0; i < w - 1; ++i) {
if (!swp) {
st('L', {y0, x0}, offset);
offset.x--;
} else {
offset.x--;
st('R', {y0, x0}, offset);
}
}
return;
}
} else {
string res;
if (x0 == x1 && x0 == 1) {
for (int i = 0; i < w-1; ++i) {
if (!swp)
st('R', {y0, x0}, offset);
offset.x++;
if (swp)
st('L', {y0, x0}, offset);
}
if (y0 == 1) {
if (!swp)
st('D', {y0, x0}, offset);
offset.y++;
if (swp)
st('U', {y0, x0}, offset);
}
else {
if (!swp)
st('U', {y0, x0}, offset);
offset.y--;
if (swp)
st('D', {y0, x0}, offset);
}
for (int i = 0; i < w-1; ++i) {
if (!swp)
st('L', {y0, x0}, offset);
offset.x--;
if (swp)
st('R', {y0, x0}, offset);
}
} else {
for (int i = 1; i < x0; ++i) {
if (!swp)
st('L', {y0, x0}, offset);
offset.x--;
if (swp)
st('R', {y0, x0}, offset);
}
if (y0 == 1) {
if (!swp)
st('D', {y0, x0}, offset);
offset.y++;
if (swp)
st('U', {y0, x0}, offset);
}
else {
if (!swp)
st('U', {y0, x0}, offset);
offset.y--;
if (swp)
st('D', {y0, x0}, offset);
}
for (int i = 1; i < x0; ++i) {
if (!swp)
st('R', {y0, x0}, offset);
offset.x++;
if (swp)
st('L', {y0, x0}, offset);
}
if (x0 == x1) return;
for (int i = 1; i < x1 - x0; ++i) {
if (!swp)
st('R', {y0, x0}, offset);
offset.x++;
if (swp)
st('L', {y0, x0}, offset);
if (((i - 1) ^ (y0 - 1)) & 1) {
if (!swp)
st('D', {y0, x0}, offset);
offset.y++;
if (swp)
st('U', {y0, x0}, offset);
}
else {
if (!swp)
st('U', {y0, x0}, offset);
offset.y--;
if (swp)
st('D', {y0, x0}, offset);
}
}
if (!swp)
st('R', {y0, x0}, offset);
offset.x++;
if (swp)
st('L', {y0, x0}, offset);
for (int i = 0; i < w - x1; ++i) {
if (!swp)
st('R', {y0, x0}, offset);
offset.x++;
if (swp)
st('L', {y0, x0}, offset);
}
if (y1 == 1) {
if (!swp)
st('U', {y0, x0}, offset);
offset.y--;
if (swp)
st('D', {y0, x0}, offset);
}
else {
if (!swp)
st('D', {y0, x0}, offset);
offset.y++;
if (swp)
st('U', {y0, x0}, offset);
}
for (int i = 0; i < w - x1; ++i) {
if (!swp)
st('L', {y0, x0}, offset);
offset.x--;
if (swp)
st('R', {y0, x0}, offset);
}
}
}
}
void solve2(int n, int m, pair<int, int> s, pair<int, int> t, pair<int, int> offset) {
s2++;
solveSmall(n, m, s.y, s.x, t.y, t.x, offset);
}
};
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;
if (!inside(h, w, s) || !inside(h, w, t)) return false;
return works(h, w, s.y - 1, s.x - 1, t.y - 1, t.x - 1);
}
pair<int, int> ot(pair<int, int> p, pair<int, int> off) {
return {p.y + off.y, p.x + off.x};
}
const int cutoff = 20;
bool vis[MAX_N + 1][MAX_N + 1];
bool run_brute(int n, int m, pair<int, int> c, pair<int, int> t, int left, pair<int, int> offset) {
if (c.x < 1 || c.x > m || c.y < 1 || c.y > n) return false;
if (vis[c.y][c.x]) return false;
if (left == 0) {
if (c != t) return false;
st('E', c, offset);
return true;
}
vis[c.y][c.x] = 1;
if (run_brute(n, m, {c.y - 1, c.x}, t, left - 1, offset)) {
st('U', c, offset);
return true;
}
if (run_brute(n, m, {c.y + 1, c.x}, t, left - 1, offset)) {
st('D', c, offset);
return true;
}
if (run_brute(n, m, {c.y, c.x - 1}, t, left - 1, offset)) {
st('L', c, offset);
return true;
}
if (run_brute(n, m, {c.y, c.x + 1}, t, left - 1, offset)) {
st('R', c, offset);
return true;
}
vis[c.y][c.x] = 0;
return false;
}
int c = 0;
void brute(int n, int m, pair<int, int> s, pair<int, int> t, pair<int, int> offset) {
c++;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) vis[i][j] = 0;
}
run_brute(n, m, s, t, n * m - 1, offset);
}
void solve_strip_hor(bool left, int n, int m, pair<int, int> offset) {
int s_idx = 0;
bool up;
pair<int, int> cp;
// cout << "here hor " << left << " " << n << " " << m << " " << offset.y << " " << offset.x << endl;
if (left) {
for (int i = 1; i <= n; ++i) {
char c = gt({i, m + 1}, offset);
if (c == 'D') {
up = 1;
s_idx = i;
break;
} else if (c == 'U') {
up = 0;
s_idx = i;
break;
}
}
st('L', {s_idx, m + 1}, offset);
cp = {s_idx, m};
} else {
for (int i = 1; i <= n; ++i) {
char c = gt({i, 0}, offset);
if (c == 'D') {
up = 1;
s_idx = i;
break;
} else if (c == 'U') {
up = 0;
s_idx = i;
break;
}
}
st('R', {s_idx, 0}, offset);
cp = {s_idx, 1};
}
if (up) {
while (cp.y != 1) {
st('U', cp, offset);
cp.y--;
}
} else {
while (cp.y != n) {
st('D', cp, offset);
cp.y++;
}
}
if (left) {
st('L', cp, offset);
cp.x--;
} else {
st('R', cp, offset);
cp.x++;
}
if (up) {
while (cp.y != n) {
st('D', cp, offset);
cp.y++;
}
} else {
while (cp.y != 1) {
st('U', cp, offset);
cp.y--;
}
}
if (left) {
st('R', cp, offset);
cp.x++;
} else {
st('L', cp, offset);
cp.x--;
}
if (up) {
while (cp.y != s_idx + 1) {
st('U', cp, offset);
cp.y--;
}
} else {
while (cp.y != s_idx - 1) {
st('D', cp, offset);
cp.y++;
}
}
if (left) {
st('R', cp, offset);
cp.x++;
} else {
st('L', cp, offset);
cp.x--;
}
}
void solve_strip_ver(bool up, int n, int m, pair<int, int> offset) {
int s_idx = 0;
bool left;
pair<int, int> cp;
// cout << "here hor " << left << " " << n << " " << m << " " << offset.y << " " << offset.x << endl;
if (up) {
for (int i = 1; i <= m; ++i) {
char c = gt({n + 1, i}, offset);
if (c == 'R') {
left = 1;
s_idx = i;
break;
} else if (c == 'L') {
left = 0;
s_idx = i;
break;
}
}
st('U', {n + 1, s_idx}, offset);
cp = {n, s_idx};
} else {
for (int i = 1; i <= m; ++i) {
char c = gt({0, i}, offset);
if (c == 'R') {
left = 1;
s_idx = i;
break;
} else if (c == 'L') {
left = 0;
s_idx = i;
break;
}
}
st('D', {0, s_idx}, offset);
cp = {1, s_idx};
}
if (left) {
while (cp.x != 1) {
st('L', cp, offset);
cp.x--;
}
} else {
while (cp.x != m) {
st('R', cp, offset);
cp.x++;
}
}
if (up) {
st('U', cp, offset);
cp.y--;
} else {
st('D', cp, offset);
cp.y++;
}
if (left) {
while (cp.x != m) {
st('R', cp, offset);
cp.x++;
}
} else {
while (cp.x != 1) {
st('L', cp, offset);
cp.x--;
}
}
if (up) {
st('D', cp, offset);
cp.y++;
} else {
st('U', cp, offset);
cp.y--;
}
if (left) {
while (cp.x != s_idx + 1) {
st('L', cp, offset);
cp.x--;
}
} else {
while (cp.x != s_idx - 1) {
st('R', cp, offset);
cp.x++;
}
}
if (up) {
st('D', cp, offset);
cp.y++;
} else {
st('U', cp, offset);
cp.y--;
}
}
void solve_m(int n, int m, pair<int, int> s, pair<int, int> t, pair<int, int> offset) {
// cout << "here: " << n << " " << m << " " << s.y << " " << s.x << " " << t.y << " " << t.x << endl;
int min_j = min(s.x, t.x);
int max_j = max(s.x, t.x);
/*for (int j = min_j - min_j % 2; j > 0; j -= 2) {*/
for (int j = 2; j > 0; j -= 2) {
if (min_j > j) {
if (ok(n, m - j, ot(s, {0, -j}), ot(t, {0, -j}))) {
solve_m(n, m - j, ot(s, {0, -j}), ot(t, {0, -j}), ot(offset, {0, j}));
solve_strip_hor(true, n, j, offset);
return;
}
}
}
/*for (int j = (m - max_j) / 2 * 2; j > 0; j -= 2) {*/
for (int j = 2; j > 0; j -= 2) {
if (max_j <= m - j) {
if (ok(n, m - j, s, t)) {
solve_m(n, m - j, s, t, offset);
solve_strip_hor(false, n, j, ot(offset, {0, m - j}));
return;
}
}
}
if (s.x > t.x) {
// cout << "reversed: " << s.y << " " << s.x << " " << t.y << " " << t.x << endl;
char c = gt(t, offset);
solve_m(n, m, t, s, offset);
rev_from(t, s, offset);
st(c, t, offset);
return;
}
vector<int> st_i;
st_i.push_back(1);
st_i.push_back(2);
if (n % 2 == 0) st_i.push_back(n);
else st_i.push_back(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, ot(t, {0, -first_m}))
&& ok(n, first_m, s, first_e)
&& ok(n, second_m, ot(t, {0, -first_m}), ot(second_e, {0, -first_m}))
) {
solve_m(n, first_m, s, first_e, offset);
st('R', first_e, offset);
solve_m(n, second_m, ot(second_e, {0, -first_m}), ot(t, {0, -first_m}), ot(offset, {0, first_m}));
return;
}
}
brute(n, m, s, t, offset);
}
int ckmid = 0;
int ckmidloop = 0;
void solve_mid(int n, int m, int j1, int j2, pair<int, int> offset) {
while (n > 2) {
ckmidloop++;
if (n * m <= cutoff) {
brute(n, m, {1, j1}, {n, j2}, offset);
return;
}
for (int j = 2 - (j1 % 2); j <= m; j += 2) {
ckmid++;
if (j == j1 && j1 != 1 && j1 != m) continue;
if (ok(n - 2, m, {1, j}, {n - 2, j2})) {
mango::solve2(2, m, {1, j1}, {2, j}, offset);
offset.y += 2;
j1 = j;
break;
}
}
st('D', {0, j1}, offset);
n -= 2;
}
mango::solve2(2, m, {1, j1}, {2, j2}, offset);
}
void solve_mid_rev(int n, int m, int j1, int j2, pair<int, int> offset) {
// {n, j2} -> {1, j1}
//cout << "called: " << n << " " << m << " " << j1 << " " << j2 << " " << offset.y << " " << offset.x << endl;
int on = n;
while (n > 2) {
ckmidloop++;
if (n * m <= cutoff) {
brute(n, m, {n, j2}, {1, j1}, offset);
return;
}
for (int j = 2 - (j2 % 2); j <= m; j += 2) {
ckmid++;
if (j == j2 && j2 != 1 && j2 != m) continue;
if (ok(n - 2, m, {n - 2, j}, {1, j1})) {
mango::solve2(2, m, {2, j2}, {1, j}, ot(offset, {n - 2, 0}));
st('U', {1, j}, ot(offset, {n - 2, 0}));
j2 = j;
break;
}
}
n -= 2;
}
mango::solve2(2, m, {2, j2}, {1, j1}, offset);
/*for (int i = 1; i <= on + 1; ++i) {
for (int j = 1; j <= m; ++j) {
cout << gt({i, j}, offset);
}
cout << endl;
}
cout << "END\n";*/
}
int scc = 0;
int chc = 0;
void solve(int n, int m, pair<int, int> s, pair<int, int> t, pair<int, int> offset) {
scc++;
if (n <= 2) {
mango::solve2(n, m, s, t, offset);
return;
}
int min_i = min(s.y, t.y);
int max_i = max(s.y, t.y);
/*for (int i = min_i - min_i % 2; i > 0; i -= 2) {*/
for (int i = 2; i > 0; i -= 2) {
if (min_i > i) {
if (ok(n - i, m, ot(s, {-i, 0}), ot(t, {-i, 0}))) {
solve(n - i, m, ot(s, {-i, 0}), ot(t, {-i, 0}), ot(offset, {i, 0}));
solve_strip_ver(true, i, m, offset);
return;
}
}
}
/*for (int i = (n - max_i) / 2 * 2; i > 0; i -= 2) {*/
for (int i = 2; i > 0; i -= 2) {
if (max_i <= n - i) {
if (ok(n - i, m, s, t)) {
solve(n - i, m, s, t, offset);
solve_strip_ver(false, i, m, ot(offset, {n - i, 0}));
return;
}
}
}
if (n <= 3 || max_i <= 2 || min_i > 2) {
solve_m(n, m, s, t, offset);
return;
}
if (s > t) {
int left_n = 2;
int right_n = 2;
int mid = n - left_n - right_n;
int color = (t.x + t.y) % 2;
for (int j1 = 1 + color; j1 <= m; j1 += 2) {
for (int j2 = 1 + color; j2 <= m; j2 += 2) {
chc++;
pair<int, int> first_e = {left_n, j1};
pair<int, int> second_e = {1, j2};
if (mid == 0 && j1 != j2) continue;
if (mid == 2 && j1 == j2 && j1 != 1 && j1 != m) continue;
if (ok(left_n, m, first_e, t)
&& ok(right_n, m, ot(s, {-(left_n + mid), 0}), second_e)
) {
mango::solve2(right_n, m, ot(s, {-(left_n + mid), 0}), second_e, ot(offset, {left_n + mid, 0}));
st('U', second_e, ot(offset, {left_n + mid, 0}));
if (mid != 0) {
solve_mid_rev(mid, m, j1, j2, ot(offset, {2, 0}));
st('U', {1, j1}, ot(offset, {2, 0}));
}
mango::solve2(left_n, m, first_e, t, offset);
return;
}
}
}
cout << "HERE: " << n << " " << m << endl;
solve_m(n, m, s, t, offset);
return;
}
int left_n = 2;
int right_n = 2;
int mid = n - left_n - right_n;
int color = (s.x + s.y) % 2;
for (int j1 = 1 + color; j1 <= m; j1 += 2) {
for (int j2 = 1 + color; j2 <= m; j2 += 2) {
chc++;
pair<int, int> first_e = {left_n, j1};
pair<int, int> second_e = {1, j2};
if (mid == 0 && j1 != j2) continue;
if (mid == 2 && j1 == j2 && j1 != 1 && j1 != m) continue;
if (ok(left_n, m, s, first_e)
&& ok(right_n, m, second_e, ot(t, {-(left_n + mid), 0}))
) {
mango::solve2(left_n, m, s, first_e, offset);
st('D', first_e, offset);
if (mid != 0) {
solve_mid(mid, m, j1, j2, ot(offset, {2, 0}));
st('D', {mid, j2}, ot(offset, {2, 0}));
}
mango::solve2(right_n, m, second_e, ot(t, {-(left_n + mid), 0}), ot(offset, {left_n + mid, 0}));
return;
}
}
}
cout << "HERE: " << n << " " << m << endl;
solve_m(n, m, s, t, offset);
}
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" << "\n";
return;
}
cout << "YES" << "\n";
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
result[i][j] = '?';
}
}
// ignore odd
if (n & 1) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
solver_all::result[i][j] = '?';
}
}
solver_all::solve(n, m, s, t, {0, 0});
for (int i = 1; i < n * m; ++i) {
char c = solver_all::result[s.y][s.x];
cout << c;
s = step(c, s);
}
cout << "\n";
return;
}
solve(n, m, s, t, {0, 0});
for (int i = 1; i < n * m; ++i) {
char c = result[s.y][s.x];
cout << c;
s = step(c, s);
}
cout << "\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 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 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 RRRRRRRRRRDLLLLLLLLLLLULDLULDL... 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 RRRULLLLDLULDLULDLULDLULDLULDL... 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 DRRDLLLUUURRDRU 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 DDDDDDDDDDDDDDDDDDDDDRRRRRRRRR... Truncated |