QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#137396	#2353. Maharajas are Going Home	S_Explosion^#	WA	531ms	120568kb	C++20	2.9kb	2023-08-10 11:57:13	2023-08-10 11:58:09

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-08-10 11:58:09]
评测

测评结果：WA
用时：531ms
内存：120568kb

查看

[2023-08-10 11:57:13]
提交

answer

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <assert.h>
#include <bitset>

template <typename Tp>
inline void read(Tp &x) {
    x = 0;
    bool f = true; char ch = getchar();
    for ( ; ch < '0' || ch > '9'; ch = getchar()) f ^= ch == '-';
    for ( ; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ 48);
    x = f ? x : -x;
}

const int N = 2e3;

int SG[N + 5][N + 5], x[N + 5], y[N + 5];
std::bitset<N * 2 + 5> col[N + 5], row[N + 5], diag[N * 2 + 5], cur;
int p1[N + 5][N * 2 + 5], p2[N + 5][N * 2 + 5], p3[N * 2 + 5][N * 2 + 5];

void solve(int x, int y) {
    if (x == 1) {
        SG[x][y] = y - 1;
    }
    else if (y == 1) {
        SG[x][y] = x - 1;
    }
    else {
        int v1 = 2 * N + 1, v2 = 2 * N + 1;
        if (x > 2 && y > 1) v1 = SG[x - 2][y - 1];
        if (x > 1 && y > 2) v2 = SG[x - 1][y - 2];
        cur = row[x] & col[y] & diag[x - y + N];
        cur[v1] = cur[v2] = 0;
        SG[x][y] = (int)cur._Find_first();
    }
    row[x][SG[x][y]] = col[y][SG[x][y]] = diag[x - y + N][SG[x][y]] = 0;
    // if (x <= 10 && y <= 10) printf("%d %d %d\n", x, y, SG[x][y]);
    if (!p1[x][SG[x][y]]) p1[x][SG[x][y]] = y;
    if (!p2[y][SG[x][y]]) p2[y][SG[x][y]] = x;
    if (!p3[x - y + N][SG[x][y]]) p3[x - y + N][SG[x][y]] = y;
}

int main() {
    for (int i = 1; i <= N; ++i) col[i].set(), row[i].set();
    for (int i = 1; i <= 2 * N; ++i) diag[i].set();
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j) solve(i, j);
    int T;
    read(T);
    while (T--) {
        int n;
        read(n);
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            read(x[i]), read(y[i]);
            ans ^= SG[x[i]][y[i]];
        }
        if (!ans) {
            printf("-1 -1 -1\n");
            continue;
        }
        for (int i = 1; i <= n; ++i) {
            int cur = ans ^ SG[x[i]][y[i]];
            int ansx = 0, ansy = 0;
            if (p1[x[i]][cur] && p1[x[i]][cur] < y[i]) ansx = x[i], ansy = p1[x[i]][cur];
            if (p2[y[i]][cur] && p2[y[i]][cur] < x[i]) ansx = p2[y[i]][cur], ansy = y[i];
            if (p3[x[i] - y[i] + N][cur] && p3[x[i] - y[i] + N][cur] < y[i]) {
                int yy = p3[x[i] - y[i] + N][cur], xx = x[i] - y[i] + yy;
                if (ansx == 0 || xx <= ansx) ansx = xx, ansy = yy;
            }
            if (x[i] > 2 && y[i] > 1 && SG[x[i] - 2][y[i] - 1] == cur) {
                if (ansx == 0 || x[i] - 2 < ansx || (x[i] - 2 == ansx && y[i] - 1 < ansy)) ansx = x[i] - 2, ansy = y[i] - 1; 
            }
            if (x[i] > 1 && y[i] > 2 && SG[x[i] - 1][y[i] - 2] == cur) {
                if (ansx == 0 || x[i] - 1 < ansx || (x[i] - 1 == ansx && y[i] - 2 < ansy)) ansx = x[i] - 1, ansy = y[i] - 2; 
            }
            if (ansx) {
                printf("%d %d %d\n", i, ansx, ansy);
                break;
            }
        }
    }
    return 0;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 520ms

memory: 120520kb

input:

output:

3 1 1
-1 -1 -1
2 1 1

result:

ok 3 lines

Test #2:

score: 0

Accepted

time: 527ms

memory: 120276kb

input:

1
1
1 1

output:

-1 -1 -1

result:

ok single line: '-1 -1 -1'

Test #3:

score: 0

Accepted

time: 485ms

memory: 120568kb

input:

output:

result:

ok 100 lines

Test #4:

score: 0

Accepted

time: 511ms

memory: 120348kb

input:

output:

result:

ok 100 lines

Test #5:

score: 0

Accepted

time: 498ms

memory: 120564kb

input:

output:

result:

ok 100 lines

Test #6:

score: 0

Accepted

time: 494ms

memory: 120560kb

input:

output:

result:

ok 100 lines

Test #7:

score: 0

Accepted

time: 481ms

memory: 120388kb

input:

output:

result:

ok 100 lines

Test #8:

score: 0

Accepted

time: 521ms

memory: 120340kb

input:

output:

result:

ok 100 lines

Test #9:

score: -100

Wrong Answer

time: 531ms

memory: 120388kb

input:

output:

1 1000 2000
2 293 1537
2 1956 1638
6 411 778
1 82 549
1 1312 528
4 776 700
1 115 17
9 1021 283
9 411 1800
1 236 1082
1 849 1864
1 627 1550
1 679 605
6 811 510
2 1734 493
9 1032 1455
4 484 204
1 464 607
3 899 541
1 126 1350
1 256 681
3 391 617
1 265 627
2 510 763
1 198 831
1 507 263
2 1047 1678
1 382...

result:

wrong answer 15th lines differ - expected: '9 1531 716', found: '6 811 510'