Task: | Ruudukko |
Sender: | Mahtimursu |
Submission time: | 2023-03-10 23:08:25 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | WRONG ANSWER | 0 |
#3 | WRONG ANSWER | 0 |
#4 | WRONG ANSWER | 0 |
#5 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | WRONG ANSWER | 0.00 s | 1, 5 | details |
#2 | WRONG ANSWER | 0.00 s | 2, 5 | details |
#3 | WRONG ANSWER | 0.00 s | 3, 5 | details |
#4 | WRONG ANSWER | 0.00 s | 4, 5 | details |
#5 | WRONG ANSWER | 0.00 s | 5 | details |
#6 | WRONG ANSWER | 0.01 s | 5 | details |
#7 | WRONG ANSWER | 0.00 s | 2, 5 | details |
#8 | WRONG ANSWER | 0.00 s | 2, 5 | details |
#9 | WRONG ANSWER | 0.00 s | 3, 5 | details |
#10 | WRONG ANSWER | 0.00 s | 3, 5 | details |
#11 | WRONG ANSWER | 0.00 s | 3, 5 | details |
#12 | WRONG ANSWER | 0.00 s | 3, 5 | details |
#13 | WRONG ANSWER | 0.00 s | 4, 5 | details |
#14 | WRONG ANSWER | 0.01 s | 5 | details |
#15 | WRONG ANSWER | 0.00 s | 3, 5 | details |
#16 | WRONG ANSWER | 0.01 s | 5 | details |
Code
#include <bits/stdc++.h>typedef long long ll;#define M 1000000007#define N (1 << 18)#define y first#define x secondusing namespace std;map<tuple<int, int, pair<int, int>, pair<int, int>>, int> dp;// FROM https://cses.fi/342/result/1233306string solveSmall(int h, int w, int y0, int x0, int y1, int x1) {if (x0 > x1 || (x0 == x1 && y0 > y1)) return solveSmall(h, w, y1, x1, y0, x0);if (h == 1) {if (x0 == 0 && x1 == w-1) return "X";if (x0 == w-1 && x1 == 0) return "X";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 "X";}}bool inside(int n, int m, pair<int, int> p) {return p.x <= m && p.y <= n && p.x > 0 && p.y > 0;}bool works(int h, int w, int y0, int x0, int y1, int x1);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 !solveSmall(h, w, y0, x0, y1, x1).empty();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 ok(int h, int w, pair<int, int> s, pair<int, int> t) {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};}// END FROMint solve(int n, int m, pair<int, int> s, pair<int, int> t) {if (n < m) return solve(m, n, {s.x, s.y}, {t.x, t.y});if (s > t) return solve(n, m, t, s);int best = n * m;if (best < 20) return best;if (dp[make_tuple(n, m, s, t)]) return dp[make_tuple(n, m, s, t)];//cout << n << " " << m << endl;int min_i = min(s.y, t.y);int max_i = max(s.y, t.y);int min_j = min(s.x, t.x);int max_j = max(s.x, t.x);// Try strippingif (min_i > 2) {return dp[make_tuple(n, m, s, t)] = solve(n - 2, m, offset(s, {-2, 0}), offset(s, {-2, 0}));}if (max_i < n - 1) {return dp[make_tuple(n, m, s, t)] = solve(n - 2, m, s, t);}if (min_j > 2) {return dp[make_tuple(n, m, s, t)] = solve(n, m - 2, offset(s, {0, -2}), offset(s, {0, -2}));}if (max_j < m - 1) {return dp[make_tuple(n, m, s, t)] = solve(n, m - 2, s, t);}// Split verticalfor (int i = min_i; i < max_i; ++i) {for (int j = 1; j <= m; ++j) {int first_n = i;int second_n = n - i;pair<int, int> first_e = {first_n, j};pair<int, int> second_e = {first_n + 1, j};// s -> first_e && t -> second_eif (inside(first_n, m, s)&& inside(second_n, m, offset(t, {-first_n, 0}))&& ok(first_n, m, s, first_e)&& ok(second_n, m, offset(t, {-first_n, 0}), offset(second_e, {-first_n, 0}))) {int cur = solve(first_n, m, s, first_e);if (cur < best) cur = max(cur, solve(second_n, m, offset(t, {-first_n, 0}), offset(second_e, {-first_n, 0})));best = min(best, cur);}// t -> first_e && s -> second_eif (inside(first_n, m, t)&& inside(second_n, m, offset(s, {-first_n, 0}))&& ok(first_n, m, t, first_e)&& ok(second_n, m, offset(s, {-first_n, 0}), offset(second_e, {-first_n, 0}))) {int cur = solve(first_n, m, t, first_e);if (cur < best) cur = max(cur, solve(second_n, m, offset(s, {-first_n, 0}), offset(second_e, {-first_n, 0})));best = min(best, cur);}}}for (int j = min_j; j < max_j; ++j) {for (int i = 1; i <= n; ++i) {int first_m = j;int second_m = m - j;pair<int, int> first_e = {i, first_m};pair<int, int> second_e = {i, first_m + 1};// s -> first_e && t -> second_e// cout << inside(n, first_m, s) << " " << inside(n, first_m, offset(t, {0, -first_m})) << " " << inside(n, first_m, t) << " " << inside(n, second_m, offset(s, {0, -first_m})) << endl;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}))) {int cur = solve(n, first_m, s, first_e);if (cur < best) cur = max(cur, solve(n, second_m, offset(t, {0, -first_m}), offset(second_e, {0, -first_m})));best = min(best, cur);}// t -> first_e && s -> second_eif (inside(n, first_m, t)&& inside(n, second_m, offset(s, {0, -first_m}))&& ok(n, first_m, t, first_e)&& ok(n, second_m, offset(s, {0, -first_m}), offset(second_e, {0, -first_m}))) {int cur = solve(n, first_m, t, first_e);if (cur < best) cur = max(cur, solve(n, second_m, offset(s, {0, -first_m}), offset(second_e, {0, -first_m})));best = min(best, cur);}}}return dp[make_tuple(n, m, s, t)] = best;}void test_case() {int n, m;int sy, sx;int ty, tx;cin >> n >> m >> sy >> sx >> ty >> tx;if (!ok(n, m, {sy, sx}, {ty, tx})) {cout << "NO" << endl;return;}cout << "YES\n";int s = solve(n, m, {sy, sx}, {ty, tx});cout << "SCORE: " << s << endl;if (s > 100) {cout << n << " " << m << " " << sy << " " << sx << " " << ty << " " << tx << endl;}cout << "CASES: " << dp.size() << endl;}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();//cout << "\n";}return 0;}
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 SCORE: 10 CASES: 25 NO NO ... Truncated |
Test 2
Group: 2, 5
Verdict: WRONG ANSWER
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: WRONG ANSWER
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 SCORE: 18 ... Truncated |
Test 4
Group: 4, 5
Verdict: WRONG ANSWER
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 SCORE: 12 CASES: 11 YES SCORE: 12 ... Truncated |
Test 5
Group: 5
Verdict: WRONG ANSWER
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 SCORE: 15 CASES: 27 YES ... Truncated |
Test 6
Group: 5
Verdict: WRONG ANSWER
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 SCORE: 12 CASES: 31 NO NO ... Truncated |
Test 7
Group: 2, 5
Verdict: WRONG ANSWER
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 SCORE: 8 CASES: 0 NO NO ... Truncated |
Test 8
Group: 2, 5
Verdict: WRONG ANSWER
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 SCORE: 10 CASES: 0 YES SCORE: 10 ... 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 SCORE: 12 CASES: 0 NO YES ... Truncated |
Test 10
Group: 3, 5
Verdict: WRONG ANSWER
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 SCORE: 15 CASES: 0 ... 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 SCORE: 18 ... Truncated |
Test 12
Group: 3, 5
Verdict: WRONG ANSWER
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: WRONG ANSWER
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 SCORE: 16 CASES: 0 YES SCORE: 16 ... Truncated |
Test 14
Group: 5
Verdict: WRONG ANSWER
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 SCORE: 12 CASES: 16 YES SCORE: 12 ... 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 SCORE: 18 CASES: 3 YES SCORE: 18 ... Truncated |
Test 16
Group: 5
Verdict: WRONG ANSWER
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 SCORE: 16 CASES: 46 YES SCORE: 16 ... Truncated |