QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#424535 | #8748. 简单博弈 | wsyear | WA | 1664ms | 14488kb | C++17 | 3.6kb | 2024-05-29 12:15:34 | 2024-05-29 12:15:34 |
Judging History
answer
// Author: Klay Thompson
// Problem: J. 简单博弈
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
template<class T>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }
using namespace std;
const int maxn = 510;
const int maxv = 500;
int sg[maxn][maxn][11];
vector<pii> tab[maxn];
vector<int> trans1, trans2, trans3;
int getid(vector<pii> vec) {
int sz = SZ(vec);
if (sz == 0) {
return 10;
} else if (sz == 1) {
return 9;
} else if (sz == 2) {
if (vec[0].fi == vec[1].fi) return 6;
if (vec[0].se == vec[1].se) return 8;
return 7;
}
vector<int> dx, dy;
for (auto [x, y] : vec) dx.emplace_back(x), dy.emplace_back(y);
sort(ALL(dx)), dx.erase(unique(ALL(dx)), dx.end());
sort(ALL(dy)), dy.erase(unique(ALL(dy)), dy.end());
if (SZ(dx) == 1 && SZ(dy) == 3) return 0;
if (SZ(dx) == 2 && SZ(dy) == 2) return 1;
if (SZ(dx) == 2 && SZ(dy) == 3) return 2;
if (SZ(dx) == 3 && SZ(dy) == 1) return 3;
if (SZ(dx) == 3 && SZ(dy) == 2) return 4;
if (SZ(dx) == 3 && SZ(dy) == 3) return 5;
assert(0);
}
int main() {
cin.tie(nullptr) -> ios::sync_with_stdio(false);
tab[0] = {{1, 1}, {1, 2}, {1, 3}};
tab[1] = {{1, 1}, {1, 2}, {2, 1}};
tab[2] = {{1, 1}, {1, 2}, {2, 3}};
tab[3] = {{1, 1}, {2, 1}, {3, 1}};
tab[4] = {{1, 1}, {2, 1}, {3, 2}};
tab[5] = {{1, 1}, {2, 2}, {3, 3}};
tab[6] = {{1, 1}, {1, 2}};
tab[7] = {{1, 1}, {2, 2}};
tab[8] = {{1, 1}, {2, 1}};
tab[9] = {{1, 1}};
rep (i, 1, maxv) rep (j, 1, maxv) rep (k, 0, 10) {
vector<pii> pos = tab[k];
int ok = 1;
for (auto [x, y] : pos) if (x > i || y > j) ok = 0;
if (!ok) continue;
map<int, int> mp;
if (i >= 4 && j >= 4 && !(i == 4 && j == 4)) {
for (int w : trans1) mp[sg[i - 1][j][w]] = 1;
for (int w : trans2) mp[sg[i][j - 1][w]] = 1;
for (int w : trans3) mp[sg[i - 1][j - 1][w]] = 1;
} else {
rep (p, 1, min(i, 4)) {
vector<pii> nxt;
for (auto [x, y] : pos) if (x != p) nxt.emplace_back(x, y);
mp[sg[i - 1][j][getid(nxt)]] = 1;
if (i == 4 && j == 4) trans1.emplace_back(getid(nxt));
}
rep (q, 1, min(j, 4)) {
vector<pii> nxt;
for (auto [x, y] : pos) if (y != q) nxt.emplace_back(x, y);
mp[sg[i][j - 1][getid(nxt)]] = 1;
if (i == 4 && j == 4) trans2.emplace_back(getid(nxt));
}
rep (p, 1, min(i, 4)) rep (q, 1, min(j, 4)) {
vector<pii> nxt;
for (auto [x, y] : pos) if (x != p && y != q) nxt.emplace_back(x, y);
mp[sg[i - 1][j - 1][getid(nxt)]] = 1;
if (i == 4 && j == 4) trans3.emplace_back(getid(nxt));
}
}
while (mp.count(sg[i][j][k])) sg[i][j][k]++;
}
int sum = 0, t;
cin >> t;
while (t--) {
int n, m, x, y;
vector<pii> pos;
cin >> n >> m;
rep (i, 1, 3) cin >> x >> y, pos.emplace_back(x, y);
sum ^= sg[n][m][getid(pos)];
}
cout << (sum ? "OvO" : "QAQ") << '\n';
}
/*
0:
ooo
xxx
xxx
1:
oox
oxx
xxx
2:
oox
xxo
xxx
3:
oxx
oxx
oxx
4:
oxx
oxx
xox
5:
oxx
xox
xxo
6:
oox
xxx
xxx
7:
oxx
xox
xxx
8:
oxx
oxx
xxx
9:
oxx
xxx
xxx
10:
xxx
xxx
xxx
*/
详细
Test #1:
score: 0
Wrong Answer
time: 1664ms
memory: 14488kb
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:
QAQ
result:
wrong answer 1st lines differ - expected: 'OvO', found: 'QAQ'