QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#430442 | #8748. 简单博弈 | ANewZhiyangfan# | WA | 557ms | 103748kb | C++14 | 5.5kb | 2024-06-03 20:23:34 | 2024-06-03 20:23:34 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
const int M = 500;
int n, m, T, ans;
map<int, int> mp[N][N];
//0 : 0w
//1 : 1w
//2 : 2w,row
//3 : 2w,col
//4 : 2w,no
//5 : 3w,row
//6 : 3w,col
//7 : 3w,2wrow2wcol
//8 : 3w,2wrow
//9 : 3w,2wcol
//10 : 3w,no
set<int> X, Y;
int dfs(int x, int y, int id) {
if (mp[x][y].count(id)) return mp[x][y][id];
if (x == 0 || y == 0) return 0;
vector<int> vec;
if (id == 0) {
vec.push_back(dfs(x - 1, y, 0));
vec.push_back(dfs(x, y - 1, 0));
vec.push_back(dfs(x - 1, y - 1, 0));
}else if (id == 1) {
if (x == 1) return dfs(x, y - 1, 0);
if (y == 1) return dfs(x - 1, y, 0);
vec.push_back(dfs(x - 1, y, 0));
vec.push_back(dfs(x, y - 1, 0));
vec.push_back(dfs(x - 1, y - 1, 0));
if (x > 1) vec.push_back(dfs(x - 1, y, 1));
if (y > 1) vec.push_back(dfs(x, y - 1, 1));
if (x > 1 && y > 1) vec.push_back(dfs(x - 1, y - 1, 1));
}else if (id == 2) {
if (y == 2) return dfs(x - 1, y, 0);
if (x == 1) return dfs(x, y - 2, 0);
vec.push_back(dfs(x - 1, y, 0));
if (x > 1) vec.push_back(dfs(x - 1, y, 2));
vec.push_back(dfs(x, y - 1, 1));
if (y > 2) vec.push_back(dfs(x, y - 1, 2));
vec.push_back(dfs(x - 1, y - 1, 0));
if (x > 1) vec.push_back(dfs(x - 1, y - 1, 1));
if (x > 1 && y > 2) vec.push_back(dfs(x - 1, y - 1, 2));
}
else if (id == 3) return dfs(y, x, 2);
else if (id == 4) {
vec.push_back(dfs(x - 1, y, 1));
if (x > 2) vec.push_back(dfs(x - 1, y, 4));
vec.push_back(dfs(x, y - 1, 1));
if (y > 2) vec.push_back(dfs(x, y - 1, 4));
vec.push_back(dfs(x - 1, y - 1, 1));
vec.push_back(dfs(x - 1, y - 1, 0));
if (x > 2) vec.push_back(dfs(x - 1, y - 1, 1));
if (y > 2) vec.push_back(dfs(x - 1, y - 1, 1));
if (x > 2 && y > 2) vec.push_back(dfs(x - 1, y - 1, 4));
}else if (id == 5) {
if (y == 3) return dfs(x - 1, y, 0);
if (x == 1) return dfs(x, y - 3, 0);
vec.push_back(dfs(x - 1, y, 0));
if (x > 1) vec.push_back(dfs(x - 1, y, 5));
vec.push_back(dfs(x, y - 1, 2));
if (y > 3) vec.push_back(dfs(x, y - 1, 5));
vec.push_back(dfs(x - 1, y - 1, 0));
if (x > 1) vec.push_back(dfs(x - 1, y - 1, 2));
if (x > 1 && y > 3) vec.push_back(dfs(x - 1, y - 1, 5));
}
else if (id == 6) return dfs(y, x, 5);
else if (id == 7) {
if (x == 2) return dfs(x, y - 1, 1);
if (y == 2) return dfs(x - 1, y, 1);
vec.push_back(dfs(x - 1, y, 1));
vec.push_back(dfs(x - 1, y, 2));
if (x > 2) vec.push_back(dfs(x - 1, y, 7));
vec.push_back(dfs(x, y - 1, 1));
vec.push_back(dfs(x, y - 1, 3));
if (y > 2) vec.push_back(dfs(x, y - 1, 7));
vec.push_back(dfs(x - 1, y - 1, 0));
vec.push_back(dfs(x - 1, y - 1, 1));
if (x > 2) vec.push_back(dfs(x - 1, y - 1, 1));
if (x > 2) vec.push_back(dfs(x - 1, y - 1, 3));
if (y > 2) vec.push_back(dfs(x - 1, y - 1, 1));
if (y > 2) vec.push_back(dfs(x - 1, y - 1, 2));
if (x > 2 && y > 2) vec.push_back(dfs(x - 1, y - 1, 7));
}else if (id == 8) {
vec.push_back(dfs(x - 1, y, 1));
vec.push_back(dfs(x - 1, y, 2));
if (x > 2) vec.push_back(dfs(x - 1, y, 8));
vec.push_back(dfs(x, y - 1, 4));
vec.push_back(dfs(x, y - 1, 2));
if (y > 3) vec.push_back(dfs(x, y - 1, 8));
vec.push_back(dfs(x - 1, y - 1, 1));
vec.push_back(dfs(x - 1, y - 1, 0));
if (x > 2) vec.push_back(dfs(x - 1, y - 1, 4));
if (x > 2) vec.push_back(dfs(x - 1, y - 1, 2));
if (y > 3) vec.push_back(dfs(x - 1, y - 1, 1));
if (y > 3) vec.push_back(dfs(x - 1, y - 1, 2));
if (x > 2 && y > 3) vec.push_back(dfs(x - 1, y - 1, 8));
}
else if (id == 9) return dfs(y, x, 8);
else {
vec.push_back(dfs(x - 1, y, 4));
if (x > 3) vec.push_back(dfs(x - 1, y, 10));
vec.push_back(dfs(x, y - 1, 4));
if (y > 3) vec.push_back(dfs(x, y - 1, 10));
vec.push_back(dfs(x - 1, y - 1, 4));
vec.push_back(dfs(x - 1, y - 1, 1));
if (x > 3) vec.push_back(dfs(x - 1, y - 1, 4));
if (y > 3) vec.push_back(dfs(x - 1, y - 1, 4));
if (x > 3 && y > 3) vec.push_back(dfs(x - 1, y - 1, 10));
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
// for (auto tmp : vec) cerr << tmp << ' ';
// cerr << '\n';
int now = 0;
while (now < vec.size() && now == vec[now]) now++;
// printf("[%d %d %d] : %d\n", x, y, id, now);
return mp[x][y][id] = now;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
X.clear(); Y.clear();
for (int i = 1; i <= 3; ++i) {
int x, y;
scanf("%d%d", &x, &y);
X.insert(x); Y.insert(y);
}
int id;
if (X.size() == 1 && Y.size() == 3) id = 5;
else if (X.size() == 3 && Y.size() == 1) id = 6;
else if (X.size() == 2 && Y.size() == 2) id = 7;
else if (X.size() == 2 && Y.size() == 3) id = 8;
else if (X.size() == 3 && Y.size() == 2) id = 9;
else id = 10;
ans ^= dfs(n, m, id);
}
if (ans) puts("OvO");
else puts("QAQ");
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 541ms
memory: 103748kb
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:
OvO
result:
ok single line: 'OvO'
Test #2:
score: -100
Wrong Answer
time: 557ms
memory: 102340kb
input:
100000 494 303 141 173 343 269 451 163 4 370 4 46 1 100 3 135 226 3 21 3 116 1 47 3 77 52 65 27 19 4 69 50 205 235 164 101 106 183 27 16 4 2 3 2 1 2 4 2 364 364 54 50 155 83 21 181 432 434 295 302 332 91 258 264 324 326 136 171 239 155 300 81 1 4 1 3 1 2 1 4 177 435 20 326 170 256 175 179 1 4 1 3 1 ...
output:
OvO
result:
wrong answer 1st lines differ - expected: 'QAQ', found: 'OvO'