QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#430418#8748. 简单博弈ANewZhiyangfan#WA 580ms104088kbC++145.4kb2024-06-03 19:58:522024-06-03 19:58:53

Judging History

This is the latest submission verdict.

  • [2024-06-03 19:58:53]
  • Judged
  • Verdict: WA
  • Time: 580ms
  • Memory: 104088kb
  • [2024-06-03 19:58:52]
  • Submitted

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;
    if (x == 1 && y == 1 && id == 1) return 0;
    if (x == 1 && y == 2 && id == 2) return 0;
    if (x == 2 && y == 1 && id == 3) return 0;
    if (x == 1 && y == 3 && id == 5) return 0;
    if (x == 3 && y == 1 && id == 6) 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 (y > 1) vec.push_back(dfs(x - 1, y, 0));
        if (x > 1) 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));
    }else if (id == 2) {
        if (y > 2) vec.push_back(dfs(x - 1, y, 0));
        if (x > 1) vec.push_back(dfs(x - 1, y, 2));
        if (x > 1) vec.push_back(dfs(x, y - 1, 1));
        if (y > 2) vec.push_back(dfs(x, y - 1, 2));
        if (y > 2 || x > 1) 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) vec.push_back(dfs(x - 1, y, 0));
        if (x > 1) vec.push_back(dfs(x - 1, y, 5));
        if (x > 1) vec.push_back(dfs(x, y - 1, 2));
        if (y > 3) vec.push_back(dfs(x, y - 1, 5));
        if (y > 3 || x > 1) 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) {
        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: 0
Wrong Answer
time: 580ms
memory: 104088kb

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'