QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#536240#4328. Dugputhhoppitree59.244865 ✓1248ms4756kbC++176.0kb2024-08-28 21:04:072024-10-24 22:21:14

Judging History

你现在查看的是测评时间为 2024-10-24 22:21:14 的历史记录

  • [2024-10-24 22:48:21]
  • 管理员手动重测本题所有提交记录
  • 测评结果:100
  • 用时:1260ms
  • 内存:4836kb
  • [2024-10-24 22:43:34]
  • 管理员手动重测本题所有提交记录
  • 测评结果:0
  • 用时:8ms
  • 内存:3868kb
  • [2024-10-24 22:23:38]
  • 管理员手动重测本题所有提交记录
  • 测评结果:0
  • 用时:8ms
  • 内存:3812kb
  • [2024-10-24 22:21:14]
  • 管理员手动重测本题所有提交记录
  • 测评结果:59.244865
  • 用时:1248ms
  • 内存:4756kb
  • [2024-08-28 21:04:07]
  • 评测
  • 测评结果:60
  • 用时:1252ms
  • 内存:4832kb
  • [2024-08-28 21:04:07]
  • 提交

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;
}

详细

Subtask #1:

score: 20
Accepted

Test #1:

score: 23.7914
Acceptable Answer
time: 4ms
memory: 3704kb

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.1895684148 correct (test case 1562)

Subtask #2:

score: 25
Accepted

Dependency #1:

100%
Accepted

Test #2:

score: 38.4516
Acceptable Answer
time: 71ms
memory: 4032kb

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.5380621489 correct (test case 1562)

Subtask #3:

score: 14.2449
Acceptable Answer

Dependency #2:

100%
Accepted

Test #3:

score: 14.2449
Acceptable Answer
time: 265ms
memory: 4024kb

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 0.9496576514 correct (test case 1172)

Subtask #4:

score: 0
Wrong Answer

Dependency #3:

94.9658%
Acceptable Answer

Test #4:

score: 0
Wrong Answer
time: 1248ms
memory: 4756kb

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: 1ms
memory: 3864kb

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:

wrong answer read 82499 but expected 1162 (test case 1)