QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#308009#8018. 染色Lazy_Labs0 0ms0kbC++143.9kb2024-01-19 13:13:512024-01-19 13:13:51

Judging History

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

  • [2024-01-19 13:13:51]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-01-19 13:13:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
inline int read() {
    int x(0);
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c <= '9' && c >= '0') x = (x << 3) + (x << 1) + c - 48, c = getchar();
    return x;
}
inline void write(int x) {
    static int sta[35];
    int top = 0;
    do {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + 48);  // 48 是 '0'
    putchar(' ');
}
const int N = 2100;
int n, nn;
bitset<N << 1> mp[N], mpp[N], vis[N];
const int dx[5] = { 0, 0, 0, 1, -1 };
const int dy[5] = { 0, 1, -1, 0, 0 };
inline void qwq(int x, int y, bool q) {
    if (q)
        vis[x][y].flip();
    for (int i = 0; i < 5; i++) mp[(x + dx[i] + nn) % nn][(y + dy[i] + nn) % nn].flip();
}
inline void print() {
    for (int i = 0; i < nn; i++) {
        for (int j = 0; j < nn; j++) cerr << mp[i][j];
        cerr << endl;
    }
    cerr << "-------------" << endl;
}
inline void awa(int q) {
    for (int i = 1; i < nn; i++) {
        for (int j = 0; j < nn; j++)
            if (mp[i - 1][j])
                qwq(i, j, q);
        // print();
    }
}
bitset<N << 1> base[N << 1], tmp, ans[N << 1], p[N << 1];
inline void insert(bitset<N << 1>& x, int id) {
    bitset<N << 1> qwq;
    for (int i = (nn << 1) - 1; ~i; i--) {
        if (!x[i])
            continue;
        if (p[i] == 0) {
            p[i] = x;
            ans[i] = qwq.flip(id);
            break;
        }
        x ^= p[i];
        qwq = qwq ^ ans[i];
    }
}
int main() {
    freopen("set.in", "r", stdin);
    freopen("set.out", "w", stdout);
    srand(time(0));
    n = read();
    nn = 1 << n;
    qwq(0, 0, 0);
    awa(0);
    for (int i = 0; i < nn; i++) {
        base[i] = (mp[0] << nn) | mp[nn - 1];
        mp[0] <<= 1;
        mp[0][0] = mp[0][nn];
        mp[0][nn] = 0;
        mp[nn - 1] <<= 1;
        mp[nn - 1][0] = mp[nn - 1][nn];
        mp[nn - 1][nn] = 0;
    }
    for (int i = 0; i < nn; i++) mp[i].reset();
    qwq(nn - 1, 0, 0);
    awa(0);
    for (int i = nn; i < nn << 1; i++) {
        base[i] = (mp[0] << nn) | mp[nn - 1];
        mp[0] <<= 1;
        mp[0][0] = mp[0][nn];
        mp[0][nn] = 0;
        mp[nn - 1] <<= 1;
        mp[nn - 1][0] = mp[nn - 1][nn];
        mp[nn - 1][nn] = 0;
    }

    // for(int i=0;i<nn<<1;i++)
    // {
    //     for(int j=0;j<nn<<1;j++)
    //     cerr<<base[i][j];cerr<<endl;
    // }

    for (int i = 0; i < nn << 1; i++) insert(base[i], i);

    // for(int i=0;i<nn<<1;i++)
    // {
    //     for(int j=0;j<nn<<1;j++)
    //     cerr<<ans[i][j];cerr<<":";
    //     for(int j=0;j<nn<<1;j++)
    //     cerr<<p[i][j];cerr<<endl;
    // }

    for (int i = 0; i < nn; i++)
        for (int j = 0; j < nn; j++) mpp[i][j] = mp[i][j] = read();
    awa(0);
    tmp = (mp[0] << nn) | mp[nn - 1];
    bitset<N << 1> qans;
    // for(int i=(nn<<1)-1;~i;i--)cerr<<tmp[i];cerr<<endl;
    for (int i = (nn << 1) - 1; ~i; i--) {
        if (!tmp[i])
            continue;
        tmp ^= p[i];
        qans ^= ans[i];
    }
    // for(int i=(nn<<1)-1;~i;i--)cerr<<qans[i];

    for (int i = 0; i < nn; i++)
        for (int j = 0; j < nn; j++) mp[i][j] = mpp[i][j];
    for (int i = 0; i < nn; i++) vis[i].reset();
    for (int i = 0; i < nn << 1; i++)
        if (qans[i]) {
            if (i < nn)
                qwq(0, i, 1);
            else
                qwq(nn - 1, i - nn, 1);
        }
    awa(1);
    // for(int i=0;i<nn;i++)
    // {
    //     for(int j=0;j<nn;j++)cerr<<mp[i][j];
    //     cerr<<endl;
    // }
    // cerr<<"-------------"<<endl;
    int tot = 0;
    for (int i = 0; i < nn; i++) tot += vis[i].count();
    printf("%d\n", tot);
    for (int i = 0; i < nn; i++)
        for (int j = vis[i]._Find_first(); j < nn; j = vis[i]._Find_next(j)) write(i), write(j), puts("");
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

input:

2
0 0 1 1
1 0 1 0
0 0 0 0
1 1 1 0

output:


result:


Test #2:

score: 0
Dangerous Syscalls

input:

2
0 0 0 1
1 0 0 0
1 1 0 1
1 0 1 1

output:


result:


Test #3:

score: 0
Dangerous Syscalls

input:

2
1 1 1 0
0 1 0 0
1 0 1 0
0 1 0 1

output:


result:


Test #4:

score: 0
Dangerous Syscalls

input:

2
1 0 1 1
1 0 1 0
0 1 1 0
1 1 1 0

output:


result:


Test #5:

score: 0
Dangerous Syscalls

input:

4
0 0 1 1 0 1 1 0 0 0 0 0 0 0 1 1
0 1 1 0 1 0 0 1 0 1 1 1 1 0 1 0
1 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0
1 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1
0 1 0 0 0 1 1 1 0 1 1 1 1 0 1 0
0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 0
1 1 1 0 1 0 1 1 0 1 0 1 1 1 0 0
1 1 1 1 0 1 1 1 0 1 1 0 0 0 1 1
0 0 0 0 1 1 1 0 1 1 0 1 1 0 0 1
0 0 1 0 1 ...

output:


result:


Test #6:

score: 0
Dangerous Syscalls

input:

4
1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1
1 0 0 1 1 1 1 1 1 0 1 1 1 0 1 1
1 1 1 0 1 0 1 0 0 0 1 1 1 1 0 0
1 0 1 0 0 1 1 0 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 0
1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0
0 0 1 1 0 0 1 1 1 0 1 0 0 0 1 0
1 0 1 1 0 1 1 0 0 0 0 1 1 0 0 1
1 1 1 1 1 0 0 0 0 1 0 1 0 0 1 0
1 0 0 0 0 ...

output:


result:


Test #7:

score: 0
Dangerous Syscalls

input:

4
1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 1
1 0 1 0 1 1 1 0 1 0 1 0 1 1 0 0
1 0 0 0 0 1 0 1 0 1 0 1 1 1 0 1
1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1
0 1 1 0 1 0 0 1 0 1 1 0 1 1 0 0
0 0 0 1 0 1 1 0 0 0 1 0 1 1 1 1
0 1 0 0 1 0 0 0 1 1 0 0 1 1 1 1
1 1 0 1 1 1 0 1 1 0 1 0 0 1 0 0
1 1 1 0 1 0 0 1 1 1 1 0 0 1 0 0
1 1 1 1 0 ...

output:


result:


Test #8:

score: 0
Dangerous Syscalls

input:

7
1 1 1 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 1 0 0 1 0 0 1 1 0 1 0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 1 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0
1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 0 1 0 0 1 ...

output:


result:


Test #9:

score: 0
Dangerous Syscalls

input:

7
1 1 0 1 0 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 1 1 0 0 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 1 0 0 1 1 0 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 1 1 0 1 1 1 1 0 1 1 0 1 0 1 1 1
1 0 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 ...

output:


result:


Test #10:

score: 0
Dangerous Syscalls

input:

7
1 0 1 1 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 1 1 0 1 0 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 0 0 0 1 0 1 0 1 1 1 1 0 1 1 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 1 0 1 1 1 0 1 0 1 0 1
1 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 1 0 0 0 0 ...

output:


result:


Test #11:

score: 0
Dangerous Syscalls

input:

11
1 1 0 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 1 1 1 1 0 1 1 1 1 0 0 1 0 1 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 0 1...

output:


result:


Test #12:

score: 0
Dangerous Syscalls

input:

11
1 1 1 1 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 0 0 0 1 0 1 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 1 1 0 0 0 0 0 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 1 1 1 1 0 0 1 0 1 0 0 1 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1...

output:


result:


Test #13:

score: 0
Dangerous Syscalls

input:

11
1 0 1 0 1 0 0 0 0 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 0 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 1 0 1 1 0 1 1 1 1 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 1 1 0 1 1 1 1 0 1 1 1 0 0 1 1 1 0 0 1 0 0 0 1 0 1 0 1 1 0 1 1 1 0 1 1 0 0 1 1 1 1 0 1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 0 1 0...

output:


result:


Test #14:

score: 0
Dangerous Syscalls

input:

11
1 1 0 1 1 1 0 0 1 0 1 0 1 1 0 0 0 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 1 0 1 1 1 1 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 1 0 0 0 0 1...

output:


result:


Test #15:

score: 0
Dangerous Syscalls

input:

11
1 1 0 0 0 0 1 0 1 1 1 0 0 1 1 0 1 1 1 1 0 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 0 1 1 1 1 1 1 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 1 1 0 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 1 1 1 1 1 0 1 0 0...

output:


result:


Test #16:

score: 0
Dangerous Syscalls

input:

11
1 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 1 1...

output:


result:


Test #17:

score: 0
Dangerous Syscalls

input:

11
0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0 0 1 0 1 1 1 0 1 1 0 0 1 0 0 1 0 1 1 0 1 0 1 1 0 0 1 1 0 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 1 1 0 1 0 0 1 0 0 0...

output:


result:


Test #18:

score: 0
Dangerous Syscalls

input:

11
0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 1 1 0 1 1 0 0 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 1 0 1 0 1 1 1 1 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 0 0 0 0 0 1...

output:


result:


Test #19:

score: 0
Dangerous Syscalls

input:

11
1 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 1 0 1 1 0 1 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 1 1 1 0 1 1 1 0 1 0 0 0 0 0 1 0 1 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 1 1 1 0 1 1 1 0...

output:


result:


Test #20:

score: 0
Dangerous Syscalls

input:

11
0 0 0 0 1 0 1 0 1 1 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 0 1 1 0 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 1 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 1 0 1 0 1 1 1 0 1 0 1 1 0 1 0 1 0 0 0 1 0 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 0 0 0 1 1 0...

output:


result: