QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#424535#8748. 简单博弈wsyearWA 1664ms14488kbC++173.6kb2024-05-29 12:15:342024-05-29 12:15:34

Judging History

This is the latest submission verdict.

  • [2024-05-29 12:15:34]
  • Judged
  • Verdict: WA
  • Time: 1664ms
  • Memory: 14488kb
  • [2024-05-29 12:15:34]
  • Submitted

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'