QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#536238#4328. Dugputhhoppitree60 1244ms5096kbC++176.0kb2024-08-28 21:03:262024-08-28 21:03:27

Judging History

你现在查看的是测评时间为 2024-08-28 21:03:27 的历史记录

  • [2024-10-24 22:48:20]
  • 管理员手动重测本题所有提交记录
  • 测评结果:85
  • 用时:1245ms
  • 内存:4836kb
  • [2024-10-24 22:43:34]
  • 管理员手动重测本题所有提交记录
  • 测评结果:0
  • 用时:1200ms
  • 内存:4792kb
  • [2024-10-24 22:23:36]
  • 管理员手动重测本题所有提交记录
  • 测评结果:0
  • 用时:1247ms
  • 内存:4832kb
  • [2024-10-24 22:21:14]
  • 管理员手动重测本题所有提交记录
  • 测评结果:59.244865
  • 用时:1237ms
  • 内存:4832kb
  • [2024-08-28 21:03:27]
  • 评测
  • 测评结果:60
  • 用时:1244ms
  • 内存:5096kb
  • [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;
}

Details

Tip: Click on the bar to expand more detailed information

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)