QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#427284#8748. 简单博弈PorNPtree#TL 0ms0kbC++175.3kb2024-06-01 11:57:062024-06-01 11:57:07

Judging History

This is the latest submission verdict.

  • [2024-06-01 11:57:07]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 0kb
  • [2024-06-01 11:57:06]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 505;

int mex(vector<int> S) {
    unordered_map<int, int> M;
    for (auto v : S) {
        M[v] = 1;
    }
    for (int i = 0; ; ++i) if (!M.count(i)) return i;
    return -1;
}

int f1[2][8][N][N];
const int g1[2][4] = {{1, 1, 1, 0}, {0, 0, 0, 0}};

int dfs1(int x, int y, int n, int m) {
    if (~f1[x][y][n][m]) return f1[x][y][n][m];
    vector<int> tp;
    for (int i = -1; i <= 1; ++i) {
        for (int j = -1; j <= 3; ++j) {
            if ((i == 1 ? !n : (i != -1 ? ((x >> i) & 1) : 0))) continue;
            if ((j == 3 ? !m : (j != -1 ? ((y >> j) & 1) : 0))) continue;
            int hv = 0;
            if (~i) {
                for (int k = 0; k <= 3 && !hv; ++k) hv |= (k == 3 ? m : !((y >> k) & 1)) && !g1[i][k];
            }
            if (~j) {
                for (int k = 0; k <= 1 && !hv; ++k) hv |= (k == 1 ? n : !((x >> k) & 1)) && !g1[k][j];
            }
            if (!hv) continue;
            int tx = (i == -1 || i == 1 ? x : x ^ (1 << i)), ty = (j == -1 || j == 3 ? y : y ^ (1 << j));
            int tn = (i == 1 ? n - 1 : n), tm = (j == 3 ? m - 1 : m);
            tp.push_back(dfs1(tx, ty, tn, tm));
        }
    }
    return f1[x][y][n][m] = mex(tp);
}

int f2[4][4][N][N];
const int g2[3][3] = {{1, 1, 0}, {1, 0, 0}, {0, 0, 0}};

int dfs2(int x, int y, int n, int m) {
    if (~f2[x][y][n][m]) return f2[x][y][n][m];
    vector<int> tp;
    for (int i = -1; i <= 2; ++i) {
        for (int j = -1; j <= 2; ++j) {
            if ((i == 2 ? !n : (i != -1 ? ((x >> i) & 1) : 0))) continue;
            if ((j == 2 ? !m : (j != -1 ? ((y >> j) & 1) : 0))) continue;
            int hv = 0;
            if (~i) {
                for (int k = 0; k <= 2 && !hv; ++k) hv |= (k == 2 ? m : !((y >> k) & 1)) && !g2[i][k];
            }
            if (~j) {
                for (int k = 0; k <= 2 && !hv; ++k) hv |= (k == 2 ? n : !((x >> k) & 1)) && !g2[k][j];
            }
            if (!hv) continue;
            int tx = (i == -1 || i == 2 ? x : x ^ (1 << i)), ty = (j == -1 || j == 2 ? y : y ^ (1 << j));
            int tn = (i == 2 ? n - 1 : n), tm = (j == 2 ? m - 1 : m);
            tp.push_back(dfs2(tx, ty, tn, tm));
        }
    }
    return f2[x][y][n][m] = mex(tp);
}

int f3[4][8][N][N];
const int g3[3][4] = {{1, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}};

int dfs3(int x, int y, int n, int m) {
    if (~f3[x][y][n][m]) return f3[x][y][n][m];
    vector<int> tp;
    for (int i = -1; i <= 2; ++i) {
        for (int j = -1; j <= 3; ++j) {
            if ((i == 2 ? !n : (i != -1 ? ((x >> i) & 1) : 0))) continue;
            if ((j == 3 ? !m : (j != -1 ? ((y >> j) & 1) : 0))) continue;
            int hv = 0;
            if (~i) {
                for (int k = 0; k <= 3 && !hv; ++k) hv |= (k == 3 ? m : !((y >> k) & 1)) && !g3[i][k];
            }
            if (~j) {
                for (int k = 0; k <= 2 && !hv; ++k) hv |= (k == 2 ? n : !((x >> k) & 1)) && !g3[k][j];
            }
            if (!hv) continue;
            int tx = (i == -1 || i == 2 ? x : x ^ (1 << i)), ty = (j == -1 || j == 3 ? y : y ^ (1 << j));
            int tn = (i == 2 ? n - 1 : n), tm = (j == 3 ? m - 1 : m);
            tp.push_back(dfs3(tx, ty, tn, tm));
        }
    }
    return f3[x][y][n][m] = mex(tp);
}

int f4[8][8][N][N];
const int g4[4][4] = {{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}};

int dfs4(int x, int y, int n, int m) {
    if (~f4[x][y][n][m]) return f4[x][y][n][m];
    vector<int> tp;
    for (int i = -1; i <= 3; ++i) {
        for (int j = -1; j <= 3; ++j) {
            if ((i == 3 ? !n : (i != -1 ? ((x >> i) & 1) : 0))) continue;
            if ((j == 3 ? !m : (j != -1 ? ((y >> j) & 1) : 0))) continue;
            int hv = 0;
            if (~i) {
                for (int k = 0; k <= 3 && !hv; ++k) hv |= (k == 3 ? m : !((y >> k) & 1)) && !g4[i][k];
            }
            if (~j) {
                for (int k = 0; k <= 3 && !hv; ++k) hv |= (k == 3 ? n : !((x >> k) & 1)) && !g4[k][j];
            }
            if (!hv) continue;
            int tx = (i == -1 || i == 3 ? x : x ^ (1 << i)), ty = (j == -1 || j == 3 ? y : y ^ (1 << j));
            int tn = (i == 3 ? n - 1 : n), tm = (j == 3 ? m - 1 : m);
            tp.push_back(dfs4(tx, ty, tn, tm));
        }
    }
    return f4[x][y][n][m] = mex(tp);
}

signed main() {
    memset(f1, -1, sizeof(f1));
    memset(f2, -1, sizeof(f2));
    memset(f3, -1, sizeof(f3));
    memset(f4, -1, sizeof(f4));
    int T; scanf("%d", &T);
    int t = 0;
    while (T--) {
        int n, m; scanf("%d%d", &n, &m);
        int a, b, c, d, e, f;
        scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f);
        if (a == c && c == e) {
            t ^= dfs1(0, 0, n - 1, m - 3);
        } else if (b == d && d == f) {
            t ^= dfs1(0, 0, n - 3, m - 1);
        } else if ((a == c || a == e || c == e) && (b == d || b == f || d == f)) {
            t ^= dfs2(0, 0, n - 2, m - 2);
        } else if (a == c || a == e || c == e) {
            t ^= dfs3(0, 0, n - 2, m - 3);
        } else if (b == d || d == f ||b == f) {
            t ^= dfs3(0, 0, n - 3, m - 2);
        } else {
            t ^= dfs4(0, 0, n - 3, m - 3);
        }
    }
    if (t) puts("OvO"); else puts("QAQ");
    return 0;
}

詳細信息

Test #1:

score: 0
Time Limit Exceeded

input:

100000
215 4
6 1
59 1
71 4
1 482
1 311
1 381
1 26
3 428
3 81
2 359
1 310
222 220
108 40
16 2
11 79
4 223
4 73
4 103
3 51
214 442
174 261
186 418
202 379
146 464
61 193
85 102
117 206
3 1
3 1
2 1
1 1
357 356
199 222
97 15
257 15
30 2
28 2
4 1
12 2
308 308
32 110
56 157
234 171
347 346
243 89
166 140
...

output:


result: