QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#427284 | #8748. 简单博弈 | PorNPtree# | TL | 0ms | 0kb | C++17 | 5.3kb | 2024-06-01 11:57:06 | 2024-06-01 11:57:07 |
Judging History
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 ...