编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#101401 #1437. [L3-2] Ice World Time Limit Exceeded 90 1591 ms 5144 K C++ / 3.0 K Veritas 2024-03-11 12:12:50
显示原始代码
#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x;
}
inline int myabs(int x) { return x < 0 ? -x : x; }
inline int dis(int a, int b, int c, int d) { return myabs(a - c) + myabs(b - d); }
// f[i][j][k][l][0/1=Alice turn][0/1/2=XD's owner][0/1/2=JJ's owner]
// draw1, alice2, bob3
struct State {
    int ax, ay, bx, by;
    int xd, jj;
    bool flag;
    bool operator<(const State b) const {
        char *p = (char *)this, *q = (char *)&b;
        for (int i = 0; i < 25; ++i) {
            if (p[i] != q[i])
                return p[i] < q[i];
        }
        return 0;
    }
};
map<State, int> f;
int n, a1, b1, c1, d1, a2, b2, c2, d2;
bool check(int a, int b, int c, int d, int flag) {
    if (flag == 1) {
        return (a == a1 && b == b1 && c == c1 && d == d1) || (a == c1 && b == d1 && c == a1 && d == b1);
    }
    return (a == a2 && b == b2 && c == c2 && d == d2) || (a == c2 && b == d2 && c == a2 && d == b2);
}
int cnt = 0;
int solve(int ax, int ay, int bx, int by, int xd, int jj, bool flag) {
    State cur = { ax, ay, bx, by, xd, jj, flag };
    if (f[cur])
        return f[cur];
    ++cnt;
    if (dis(ax, ay, bx, by) == 1) {
        if (xd)
            return f[cur] = xd + 1;
    }
    if (ax == bx || ay == by) {
        if (jj)
            return f[cur] = jj + 1;
    }
    if (ax == n && ay == n && bx == 1 && by == 1) {
        return f[cur] = 1;
    }
    // printf("%d %d %d %d %d %d %d\n",ax,ay,bx,by,xd,jj,(int)flag);
    if (flag) {
        // alice turn
        int tmp1 = 3, tmp2 = 3;
        if (ax < n) {
            int nxd = xd, njj = jj;
            if (check(ax, ay, ax + 1, ay, 1) && xd == 0)
                nxd = 1;
            if (check(ax, ay, ax + 1, ay, 2) && jj == 0)
                njj = 1;
            tmp1 = solve(ax + 1, ay, bx, by, nxd, njj, !flag);
        }
        if (ay < n) {
            int nxd = xd, njj = jj;
            if (check(ax, ay, ax, ay + 1, 1) && xd == 0)
                nxd = 1;
            if (check(ax, ay, ax, ay + 1, 2) && jj == 0)
                njj = 1;
            tmp2 = solve(ax, ay + 1, bx, by, nxd, njj, !flag);
        }
        if (tmp1 == 2 || tmp2 == 2)
            return f[cur] = 2;
        if (tmp1 == 3 && tmp2 == 3)
            return f[cur] = 3;
        return f[cur] = 1;
    } else {
        // bob turn
        int tmp1 = 2, tmp2 = 2;
        if (bx > 1) {
            int nxd = xd, njj = jj;
            if (check(bx, by, bx - 1, by, 1) && xd == 0)
                nxd = 2;
            if (check(bx, by, bx - 1, by, 2) && jj == 0)
                njj = 2;
            tmp1 = solve(ax, ay, bx - 1, by, nxd, njj, !flag);
        }
        if (by > 1) {
            int nxd = xd, njj = jj;
            if (check(bx, by, bx, by - 1, 1) && xd == 0)
                nxd = 2;
            if (check(bx, by, bx, by - 1, 2) && jj == 0)
                njj = 2;
            tmp2 = solve(ax, ay, bx, by - 1, nxd, njj, !flag);
        }
        if (tmp1 == 3 || tmp2 == 3)
            return f[cur] = 3;
        if (tmp1 == 2 && tmp2 == 2)
            return f[cur] = 2;
        return f[cur] = 1;
    }
}
void work() {
    n = read();
    a1 = read();
    b1 = read();
    c1 = read();
    d1 = read();
    a2 = read();
    b2 = read();
    c2 = read();
    d2 = read();
    f.clear();
    cnt = 0;
    switch (solve(1, 1, n, n, 0, 0, 1)) {
        case 1:
            puts("0");
            break;
        case 2:
            puts("Alice");
            break;
        case 3:
            puts("Bob");
            break;
    }
    // cout<<f.size()<<endl<<cnt<<endl;
    // for(auto x:f){
    //   printf("res=%d\t,state={%d %d %d %d %d %d
    //   %d}\n",x.second,x.first.ax,x.first.ay,x.first.bx,x.first.by,
    //                                                 x.first.xd,x.first.jj,(int)x.first.flag);
    // }
}
int main() {
    int T = read();
    while (T--) work();
}
子任务 #1
Time Limit Exceeded
得分:90
测试点 #1
Accepted
得分:100
用时:3 ms
内存:264 KiB

输入文件(1.in

20
2 2 1 2 2 1 1 1 2
2 1 1 2 1 1 1 1 2
2 2 1 2 2 2 1 2 2
2 1 2 2 2 2 1 2 2
2 1 1 1 2 1 1 1 2
2 1 1 2
<262 bytes omitted>

答案文件(1.out

Alice
Alice
Bob
Bob
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alic
<14 bytes omitted>

用户输出

Alice
Alice
Bob
Bob
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice

系统信息

Exited with return code 0
测试点 #2
Accepted
得分:100
用时:5 ms
内存:256 KiB

输入文件(2.in

20
5 5 3 5 4 2 4 3 4
5 2 3 3 3 2 2 2 3
4 2 1 2 2 3 4 4 4
6 1 2 1 3 1 2 2 2
6 5 1 5 2 6 5 6 6
4 4 3 4
<262 bytes omitted>

答案文件(2.out

Bob
Alice
Bob
Alice
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Bob
Alice
Alice
Bob
Bob
Alice
Alice

用户输出

Bob
Alice
Bob
Alice
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Bob
Alice
Alice
Bob
Bob
Alice
Alice

系统信息

Exited with return code 0
测试点 #3
Accepted
得分:100
用时:6 ms
内存:384 KiB

输入文件(3.in

20
3 1 3 2 3 1 2 1 3
6 6 2 6 3 5 4 5 5
4 4 2 4 3 1 2 2 2
3 1 3 2 3 2 2 3 2
3 2 2 3 2 1 3 2 3
5 4 1 5
<262 bytes omitted>

答案文件(3.out

Alice
Bob
Alice
0
Bob
Bob
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
0
Alice
Bob
Bob
Alice
Bob

用户输出

Alice
Bob
Alice
0
Bob
Bob
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
0
Alice
Bob
Bob
Alice
Bob

系统信息

Exited with return code 0
测试点 #4
Accepted
得分:100
用时:5 ms
内存:352 KiB

输入文件(4.in

20
5 4 3 4 4 2 3 2 4
4 3 4 4 4 3 4 4 4
3 2 1 2 2 2 3 3 3
4 1 4 2 4 1 1 1 2
4 1 1 1 2 4 1 4 2
6 3 4 3
<262 bytes omitted>

答案文件(4.out

Alice
Bob
Bob
Alice
Alice
Alice
Bob
Bob
Alice
Alice
Bob
Bob
Alice
Alice
Bob
Alice
Alice
Alice
Bob
Bo
<2 bytes omitted>

用户输出

Alice
Bob
Bob
Alice
Alice
Alice
Bob
Bob
Alice
Alice
Bob
Bob
Alice
Alice
Bob
Alice
Alice
Alice
Bob
Bob

系统信息

Exited with return code 0
测试点 #5
Accepted
得分:100
用时:6 ms
内存:248 KiB

输入文件(5.in

20
3 2 2 3 2 1 1 1 2
6 5 5 5 6 1 5 2 5
3 2 3 3 3 2 1 3 1
5 1 3 1 4 2 3 2 4
5 2 3 3 3 2 5 3 5
4 1 2 1
<262 bytes omitted>

答案文件(5.out

Alice
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Bob
0
Alice
Alice
Bob
Alice

用户输出

Alice
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Bob
0
Alice
Alice
Bob
Alice

系统信息

Exited with return code 0
测试点 #6
Accepted
得分:100
用时:28 ms
内存:508 KiB

输入文件(6.in

20
9 4 2 4 3 4 7 5 7
9 3 7 4 7 4 4 5 4
10 2 9 3 9 9 8 10 8
9 4 1 5 1 7 7 7 8
9 8 7 9 7 4 1 5 1
10 7 
<276 bytes omitted>

答案文件(6.out

Bob
Alice
Bob
Bob
Alice
Bob
Alice
Bob
Alice
Alice
Alice
Bob
Bob
Bob
0
0
Alice
Alice
Alice
Bob

用户输出

Bob
Alice
Bob
Bob
Alice
Bob
Alice
Bob
Alice
Alice
Alice
Bob
Bob
Bob
0
0
Alice
Alice
Alice
Bob

系统信息

Exited with return code 0
测试点 #7
Accepted
得分:100
用时:28 ms
内存:384 KiB

输入文件(7.in

20
10 4 2 5 2 8 1 8 2
9 9 3 9 4 6 3 7 3
10 4 6 5 6 3 4 3 5
9 7 9 8 9 1 6 2 6
9 7 7 7 8 6 8 7 8
9 4 3
<274 bytes omitted>

答案文件(7.out

Alice
Bob
Alice
0
Bob
Bob
Bob
Alice
Alice
Alice
Bob
Bob
Bob
Alice
Alice
Alice
Bob
Alice
Alice
Alice

用户输出

Alice
Bob
Alice
0
Bob
Bob
Bob
Alice
Alice
Alice
Bob
Bob
Bob
Alice
Alice
Alice
Bob
Alice
Alice
Alice

系统信息

Exited with return code 0
测试点 #8
Accepted
得分:100
用时:244 ms
内存:4864 KiB

输入文件(8.in

20
12 11 6 11 7 4 7 5 7
10 3 7 4 7 7 1 8 1
18 9 16 10 16 12 10 12 11
22 12 13 13 13 4 9 5 9
5 4 2 4 
<344 bytes omitted>

答案文件(8.out

Alice
Alice
Bob
Alice
Bob
Alice
Bob
Bob
Bob
Bob
Alice
Alice
Alice
Bob
Bob
Alice
Bob
Alice
Bob
Alice

用户输出

Alice
Alice
Bob
Alice
Bob
Alice
Bob
Bob
Bob
Bob
Alice
Alice
Alice
Bob
Bob
Alice
Bob
Alice
Bob
Alice

系统信息

Exited with return code 0
测试点 #9
Accepted
得分:100
用时:245 ms
内存:4088 KiB

输入文件(9.in

20
5 3 2 4 2 4 2 4 3
6 5 3 5 4 3 2 4 2
5 4 5 5 5 4 1 5 1
8 5 6 5 7 7 5 7 6
21 3 4 3 5 18 21 19 21
15
<339 bytes omitted>

答案文件(9.out

Alice
0
Bob
Bob
Bob
Alice
Bob
Bob
Alice
Alice
Alice
Alice
Alice
Bob
Bob
Bob
Bob
Bob
Alice
Alice

用户输出

Alice
0
Bob
Bob
Bob
Alice
Bob
Bob
Alice
Alice
Alice
Alice
Alice
Bob
Bob
Bob
Bob
Bob
Alice
Alice

系统信息

Exited with return code 0
测试点 #10
Time Limit Exceeded
得分:0
用时:1021 ms
内存:5144 KiB

输入文件(10.in

20
30 16 8 16 9 9 24 9 25
30 6 6 7 6 15 23 16 23
30 28 23 28 24 8 12 9 12
30 22 24 23 24 28 28 29 28
<399 bytes omitted>

答案文件(10.out

Bob
Bob
0
Bob
Alice
Bob
Bob
Alice
Bob
Bob
Bob
Alice
Alice
Bob
Alice
Bob
Bob
Alice
Alice
Bob

用户输出

Bob
Bob
0
Bob
Alice
Bob
Bob
Alice
Bob
Bob
Bob
Alice
Alice
Bob
Alice
Bob
Bob
Alice
Alice
Bob