QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #706560 | #4328. Dugput | TheZone | 100 ✓ | 1284ms | 5096kb | C++20 | 10.1kb | 2024-11-03 12:13:13 | 2024-11-03 12:13:14 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
string rep(string s, char U, char D, char L, char R) {
for_each(s.begin(), s.end(), [&](char &x){ x += 'a' - 'A';});
replace(s.begin(), s.end(), 'u', U), replace(s.begin(), s.end(), 'd', D);
replace(s.begin(), s.end(), 'l', L), replace(s.begin(), s.end(), 'r', R);
return s;
}
string rev(string s) {
reverse(s.begin(), s.end()); return rep(s, 'D', 'U', 'R', 'L');
}
int calc(int n, int m, int a, int b, int c, int d) {
if (n > m) return calc(m, n, b, a, d, c);
if (a > c) return calc(n, m, n - a + 1, b, n - c + 1, d);
if (b > d) return calc(n, m, a, m - b + 1, c, m - d + 1);
if (a == c && b == d) return 0;
if (n == 1) return abs(b - d);
if (n == 2 && a != c && d - b <= 1) return max(b + d - 1, m + m - b - d + 1);
if ((n * m) & 1) return n * m - 1 - ((a + b) & 1) - ((c + d) & 1);
if (n == 3 && ((a + b + c + d) & 1) && ((d - b >= 2 && ((a + b) & 1)) || (a == 2 && c == 2 && (b & 1)))) return n * m - 3;
return n * m - 1 - !((a + b + c + d) & 1);
}
void Nxt(int ty, int n, int m, int a, int b, int &c, int &d, char &dir) {
c = a, d = b;
if ((a == 1 && (b != (!ty ? m : 1))) || (a == n && (b != (!ty ? 1 : m)))) {
if (ty ^ (a == 1)) ++d, dir = 'R';
else --d, dir = 'L';
} else {
if (ty ^ (b == 1)) --c, dir = 'U';
else ++c, dir = 'D';
}
}
string Solve(int n, int m, int a, int b, int c, int d) {
int V = calc(n, m, a, b, c, d);
if (n > m) return rep(Solve(m, n, b, a, d, c), 'L', 'R', 'U', 'D');
if (a > c) return rep(Solve(n, m, n - a + 1, b, n - c + 1, d), 'D', 'U', 'L', 'R');
if (b > d) return rep(Solve(n, m, a, m - b + 1, c, m - d + 1), 'U', 'D', 'R', 'L');
if (n == 1) return string(d - b, 'R');
if (n == 2 && a != c && abs(b - d) <= 1) {
if (b + d - 1 > m + m - b - d + 1) return string(b - 1, 'L') + "D" + string(d - 1, 'R');
return string(m - b, 'R') + "D" + string(m - d, 'L');
}
for (int i = a; i < c; ++i) for (int j = 1; j <= m; ++j)
if (calc(i, m, a, b, i, j) + calc(n - i, m, 1, j, c - i, d) + 1 == V)
return Solve(i, m, a, b, i, j) + "D" + Solve(n - i, m, 1, j, c - i, d);
for (int i = b; i < d; ++i) for (int j = 1; j <= n; ++j)
if (calc(n, i, a, b, j, i) + calc(n, m - i, j, 1, c, d - i) + 1 == V)
return Solve(n, i, a, b, j, i) + "R" + Solve(n, m - i, j, 1, c, d - i);
int f1 = (a == 1 || a == n || b == 1 || b == m), f2 = (c == 1 || c == n || d == 1 || d == m);
if ((f1 || f2) && n > 3) {
int fl = 0;
if (!f1 && f2) swap(f1, f2), fl = 1, swap(a, c), swap(b, d);
string S;
int ty = (a == 1 && b == 2) || (a == 2 && b == m) || (a == n && b == m - 1) || (a == n - 1 && b == 1);
int ta = a, tb = b;
while (1) {
int ox, oy; char dir;
Nxt(ty, n, m, a, b, ox, oy, dir);
if (ox == ta && oy == tb) {
if (a == 1) ++a, S += "D";
else if (a == n) --a, S += "U";
else if (b == 1) ++b, S += "R";
else --b, S += "L";
break;
}
a = ox, b = oy, S += dir;
}
S += Solve(n - 2, m - 2, a - 1, b - 1, c - 1, d - 1);
return fl ? rev(S) : S;
}
if (n != 3) {
string S;
int fl = !(n & 1);
if (fl) swap(n, m), swap(a, b), swap(c, d);
if (a > ((n + 1) >> 1)) return rep(Solve(n, m, n - a + 1, b, n - c + 1, d), 'D', 'U', 'L', 'R');
S += string(a - 1, 'U');
S += string(m - b, 'R');
S += string(n - 1, 'D');
S += string(m - 1, 'L');
S += string(n - 1, 'U');
S += "R";
for (int i = 1; i <= (a >> 1); ++i) {
S += string(b - 3, 'R') + "D" + string(b - 3, 'L') + "D";
}
for (int i = 1; i <= (m >> 1) - 1; ++i) {
S += string(n - a - 2, 'D') + "R" + string(n - a - 2, 'U') + (i != (m >> 1) - 1 ? "R" : "U");
}
for (int i = 1; i <= ((m - b - 1) >> 1); ++i) {
S += string(a - 2, 'U') + "L" + string(a - 2, 'D') + (i != ((m - b - 1) >> 1) ? "L" : "");
}
return fl ? rep(S, 'L', 'R', 'U', 'D') : S;
}
if (a == 3 || (a == 2 && c == 3)) return rev(rep(Solve(n, m, n - c + 1, m - d + 1, n - a + 1, m - b + 1), 'D', 'U', 'R', 'L'));
if (a == 1 && b == d && calc(n, b - 1, 1, b - 1, c ^ 1, b - 1) + calc(n, m - b, c ^ 1, 1, c, 1) + 4 == V) {
return "L" + Solve(n, b - 1, 1, b - 1, c ^ 1, b - 1) + "RR" + Solve(n, m - b, c ^ 1, 1, c, 1) + "L";
}
if (a == 1 && b == d && calc(n, m - b, 1, 1, c ^ 1, 1) + calc(n, b - 1, c ^ 1, b - 1, c, b - 1) + 4 == V) {
return "R" + Solve(n, m - b, 1, 1, c ^ 1, 1) + "LL" + Solve(n, b - 1, c ^ 1, b - 1, c, b - 1) + "R";
}
string S;
S += string(m - b, 'R');
S += "D";
for (int i = 1; i <= (m - b - 1) >> 1; ++i) S += "DLUL";
S += "L";
for (int i = 1; i <= (b - 1) >> 1; ++i) S += "LULD";
S += "D";
S += string(b, 'R');
return S;
}
void printGrid(int n, int m, int a, int b, int c, int d, string S) {
vector< vector<char> > z(n * 2, vector<char>(m * 3 - 1, ' '));
z[a * 2 - 1][b * 3 - 2] = z[c * 2 - 1][d * 3 - 2] = '*';
for (auto o : S) {
if (o == 'R') z[a * 2 - 1][b * 3 - 1] = z[a * 2 - 1][b * 3] = '-', ++b;
else if (o == 'L') --b, z[a * 2 - 1][b * 3 - 1] = z[a * 2 - 1][b * 3] = '-';
else if (o == 'D') z[a * 2][b * 3 - 2] = '|', ++a;
else --a, z[a * 2][b * 3 - 2] = '|';
}
for (int i = 1; i <= n * 2 - 1; ++i, puts("")) {
for (int j = 1; j <= m * 3 - 2; ++j) putchar(z[i][j] != '*' && (i & 1) && (j % 3 == 1) ? 'o' : z[i][j]);
}
}
signed main() {
int type, T; scanf("%d%d", &type, &T);
while (T--) {
int n, m, a, b, c, d; scanf("%d%d%d%d%d%d", &n, &m, &a, &b, &c, &d);
if (type != 5) printGrid(n, m, a, b, c, d, Solve(n, m, a, b, c, d));
else printf("%d\n", calc(n, m, a, b, c, d) + 1);
}
return 0;
}
/*#include <bits/stdc++.h>
using namespace std;
string rep(string s, char U, char D, char L, char R) {
for_each(s.begin(), s.end(), [&](char &x){ x += 'a' - 'A';});
replace(s.begin(), s.end(), 'u', U), replace(s.begin(), s.end(), 'd', D);
replace(s.begin(), s.end(), 'l', L), replace(s.begin(), s.end(), 'r', R);
return s;
}
string rev(string s) {
reverse(s.begin(), s.end()); return rep(s, 'D', 'U', 'R', 'L');
}
int calc(int n, int m, int a, int b, int c, int d) {
if (n > m) return calc(m, n, b, a, d, c);
if (a > c) return calc(n, m, n - a + 1, b, n - c + 1, d);
if (b > d) return calc(n, m, a, m - b + 1, c, m - d + 1);
if (a == c && b == d) return 0;
if (n == 1) return abs(b - d);
if (n == 2 && a != c && d - b <= 1) return max(b + d - 1, m + m - b - d + 1);
if ((n * m) & 1) return n * m - 1 - ((a + b) & 1) - ((c + d) & 1);
if (n == 3 && ((a + b + c + d) & 1) && ((d - b >= 2 && ((a + b) & 1)) || (a == 2 && c == 2 && (b & 1)))) return n * m - 3;
return n * m - 1 - !((a + b + c + d) & 1);
}
void Nxt(int ty, int n, int m, int a, int b, int &c, int &d, char &dir) {
c = a, d = b;
if ((a == 1 && (b != (!ty ? m : 1))) || (a == n && (b != (!ty ? 1 : m)))) {
if (ty ^ (a == 1)) ++d, dir = 'R';
else --d, dir = 'L';
} else {
if (ty ^ (b == 1)) --c, dir = 'U';
else ++c, dir = 'D';
}
}
string Solve(int n, int m, int a, int b, int c, int d) {
int V = calc(n, m, a, b, c, d);
if (n > m) return rep(Solve(m, n, b, a, d, c), 'L', 'R', 'U', 'D');
if (a > c) return rep(Solve(n, m, n - a + 1, b, n - c + 1, d), 'D', 'U', 'L', 'R');
if (b > d) return rep(Solve(n, m, a, m - b + 1, c, m - d + 1), 'U', 'D', 'R', 'L');
if (n == 1) return string(d - b, 'R');
if (n == 2 && a != c && abs(b - d) <= 1) {
if (b + d - 1 > m + m - b - d + 1) return string(b - 1, 'L') + "D" + string(d - 1, 'R');
return string(m - b, 'R') + "D" + string(m - d, 'L');
}
for (int i = a; i < c; ++i) for (int j = 1; j <= m; ++j)
if (calc(i, m, a, b, i, j) + calc(n - i, m, 1, j, c - i, d) + 1 == V)
return Solve(i, m, a, b, i, j) + "D" + Solve(n - i, m, 1, j, c - i, d);
for (int i = b; i < d; ++i) for (int j = 1; j <= n; ++j)
if (calc(n, i, a, b, j, i) + calc(n, m - i, j, 1, c, d - i) + 1 == V)
return Solve(n, i, a, b, j, i) + "R" + Solve(n, m - i, j, 1, c, d - i);
int f1 = (a == 1 || a == n || b == 1 || b == m), f2 = (c == 1 || c == n || d == 1 || d == m);
if ((f1 || f2) && n > 3) {
int fl = 0;
if (!f1 && f2) swap(f1, f2), fl = 1, swap(a, c), swap(b, d);
string S;
int ty = (a == 1 && b == 2) || (a == 2 && b == m) || (a == n && b == m - 1) || (a == n - 1 && b == 1);
int ta = a, tb = b;
while (1) {
int ox, oy; char dir;
Nxt(ty, n, m, a, b, ox, oy, dir);
if (ox == ta && oy == tb) {
if (a == 1) ++a, S += "D";
else if (a == n) --a, S += "U";
else if (b == 1) ++b, S += "R";
else --b, S += "L";
break;
}
a = ox, b = oy, S += dir;
}
S += Solve(n - 2, m - 2, a - 1, b - 1, c - 1, d - 1);
return fl ? rev(S) : S;
}
if (n != 3) {
string S;
int fl = !(n & 1);
if (fl) swap(n, m), swap(a, b), swap(c, d);
if (a > ((n + 1) >> 1)) return rep(Solve(n, m, n - a + 1, b, n - c + 1, d), 'D', 'U', 'L', 'R');
S += string(a - 1, 'U');
S += string(m - b, 'R');
S += string(n - 1, 'D');
S += string(m - 1, 'L');
S += string(n - 1, 'U');";
}
string S;
S += string(m - b, 'R');
S += "D";
for (int i = 1; i <= (m - b - 1) >> 1; ++i) S += "DLUL";
S += "L";
int n, m, a, b, c, d; scanf("%d%d%d%d%d%d", &n, &m, &a, &b, &c, &d);
if (type != 5) printGrid(n, m, a, b, c, d, Solve(n, m, a, b, c, d));
else printf("%d\n", calc(n, m, a, b, c, d) + 1);
}
return 0;
}*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 8ms
memory: 3960kb
input:
1 1562 15 6 1 6 15 1 15 6 5 6 11 1 15 6 15 2 1 5 15 6 1 6 1 3 15 6 15 6 11 6 15 6 1 1 4 2 15 6 2 1 9 2 15 6 4 5 9 4 15 6 4 5 4 6 15 6 9 2 3 2 15 6 9 2 6 5 2 41 1 41 2 1 2 41 1 24 2 9 2 41 2 2 1 10 2 41 1 1 1 14 2 41 2 1 1 10 2 41 2 16 2 17 2 41 1 28 2 35 2 41 2 9 1 36 2 41 1 18 ...
output:
o--o--o o--o * | | | | | o--o o o o o | | | | | o--o o o o o | | | | | o--o o o o o | | | | | o--o o o o o | | | | | o--o o o o o | | | | | o--o o o o o | | | | | o--o o o o o | | | | | o--o o o o o | | | ...
result:
points 1.0 correct (test case 1562)
Subtask #2:
score: 25
Accepted
Dependency #1:
100%
Accepted
Test #2:
score: 25
Accepted
time: 83ms
memory: 3996kb
input:
2 1562 500 1 1 1 500 1 500 1 52 1 76 1 500 1 24 1 243 1 500 1 1 1 386 1 500 1 1 1 10 1 500 1 340 1 117 1 500 1 298 1 363 1 500 1 300 1 103 1 500 1 370 1 383 1 12 83 12 1 12 83 12 83 12 27 12 65 12 83 1 22 1 78 12 83 1 83 12 69 12 83 1 83 2 83 12 83 1 83 2 60 12 83 10 83 11 14 12 83...
output:
* | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | o | ...
result:
points 1.0 correct (test case 1562)
Subtask #3:
score: 15
Accepted
Dependency #2:
100%
Accepted
Test #3:
score: 15
Accepted
time: 279ms
memory: 4048kb
input:
3 1172 500 3 500 3 1 3 500 3 332 1 425 1 500 3 390 1 270 3 500 3 1 1 293 3 500 3 500 1 284 1 500 3 1 3 55 2 500 3 314 1 457 2 500 3 68 2 261 2 500 3 68 2 69 3 500 3 299 2 376 2 500 3 299 2 299 1 500 3 500 1 1 1 500 3 103 1 300 1 500 3 142 1 113 1 500 3 1 1 76 3 500 3 1 1 439 1 500 ...
output:
o--o * | | | o o o | | | o o o | | | o o o | | | o o o | | | o o o | | | o o o | | | o o o | | | o o o | | | o o o | | | o o o | | | o o o | | | o o o | | | o o o | | | o o o | | | o o o | | | o o o | | | o o o | | | o o o | |...
result:
points 1.0 correct (test case 1172)
Subtask #4:
score: 25
Accepted
Dependency #3:
100%
Accepted
Test #4:
score: 25
Accepted
time: 1284ms
memory: 5096kb
input:
4 1562 165 500 1 500 165 500 165 500 78 500 1 401 165 500 165 469 104 500 165 500 1 1 165 298 165 500 165 1 1 499 165 500 165 1 4 122 165 500 8 1 85 361 165 500 112 191 152 254 165 500 112 191 114 190 165 500 49 106 64 350 165 500 49 106 48 108 22 500 22 500 22 1 22 500 20 1 1 387 22 ...
output:
o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--o--...
result:
points 1.0 correct (test case 1562)
Subtask #5:
score: 15
Accepted
Test #5:
score: 15
Accepted
time: 1ms
memory: 3788kb
input:
5 1562 165 500 1 500 165 500 165 500 78 500 1 401 165 500 165 469 104 500 165 500 1 1 165 298 165 500 165 1 1 499 165 500 165 1 4 122 165 500 8 1 85 361 165 500 112 191 152 254 165 500 112 191 114 190 165 500 49 106 64 350 165 500 49 106 48 108 22 500 22 500 22 1 22 500 20 1 1 387 22 ...
output:
82499 82499 82499 82500 82499 82499 82500 82500 82500 82500 82500 11000 11000 10999 10999 10999 11000 10999 11000 11000 11000 10999 10499 10500 10500 10500 10500 10500 10500 10500 10500 10500 10499 30000 30000 29999 29999 29999 30000 30000 29999 30000 29999 30000 39999 39999 40000 40000 40000 40000 ...
result:
ok good job! (1562 test cases)