CSES - Putka Open 2020 – 4/5 - Results
Submission details
Task:Ruudukko
Sender:Mahtimursu
Submission time:2023-03-10 23:08:25 +0200
Language:C++ (C++17)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
Test results
testverdicttimegroup
#10.00 s1, 5details
#20.00 s2, 5details
#30.00 s3, 5details
#40.00 s4, 5details
#50.00 s5details
#60.01 s5details
#70.00 s2, 5details
#80.00 s2, 5details
#90.00 s3, 5details
#100.00 s3, 5details
#110.00 s3, 5details
#120.00 s3, 5details
#130.00 s4, 5details
#140.01 s5details
#150.00 s3, 5details
#160.01 s5details

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;
map<tuple<int, int, pair<int, int>, pair<int, int>>, int> dp;
// FROM https://cses.fi/342/result/1233306
string 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 FROM
int 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 stripping
if (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 vertical
for (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_e
if (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_e
if (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_e
if (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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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