QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#536238 | #4328. Dugput | hhoppitree | 60 | 1244ms | 5096kb | C++17 | 6.0kb | 2024-08-28 21:03:26 | 2024-08-28 21:03:27 |
Judging History
你现在查看的是测评时间为 2024-08-28 21:03:27 的历史记录
- [2024-08-28 21:03:26]
- 提交
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 != 0) 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;
}
详细
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 8ms
memory: 3992kb
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: 75ms
memory: 4064kb
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: 259ms
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: 0
Wrong Answer
Dependency #3:
100%
Accepted
Test #4:
score: 0
Wrong Answer
time: 1221ms
memory: 4820kb
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:
wrong answer invalid map: (1, 1) is , but it should be either o or * (test case 1349)
Subtask #5:
score: 0
Wrong Answer
Test #5:
score: 0
Wrong Answer
time: 1244ms
memory: 5096kb
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:
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:
wrong output format Expected integer, but "o--o--o--o--o--o--o--o--o--o--...o--o--o--o--o--o--o--o--o--o--*" found (test case 1)