QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#307966#7974. 染色Doqe0 783ms24216kbC++142.7kb2024-01-19 12:13:052024-01-19 12:13:06

Judging History

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

  • [2024-01-19 12:13:06]
  • 评测
  • 测评结果：0
  • 用时：783ms
  • 内存：24216kb
查看
  • [2024-01-19 12:13:05]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=2048;
// bitset<2048*2048>a[2048*2048];
int ch[2048*2048],n;int tt=0;
int pos[N][N];
bitset<N>F[N],b[N];
int G[N][N];
// bool solve()
// {
//     int n=tt;
//     for(int i=1;i<=n;++i)
//     {
//         // cerr<<i<<endl;
//         for(int j=i;j<=n;++j)
//             if(a[j][i]){swap(a[j],a[i]);break;}
//         if(!a[i][i])continue;
//         for(int j=1;j<=n;++j)if(i!=j&&a[j][i])a[j]^=a[i];
//     }
//     for(int i=1;i<=n;++i)if(a[i][tt+1])ch[i]=1;
//     return true;
// }
bitset<N>c[N];
vector<pair<int,int>>to;
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;n=1<<n;
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
        {
            int w;cin>>w;
            b[i][j]=w;
        }
    F[1][1]=1;
    for(int u=4;u<=n;u<<=1)
    {
        // cerr<<"SOLVE: "<<u<<" "<<n<<endl;
        for(int i=0;i<u;++i)
            for(int j=0;j<u;++j)
                G[i][j]=0;
        for(int i=0;i<u/2;++i)
            for(int j=0;j<u/2;++j)
                G[i+u/4][j]^=F[i][j],
                G[i+u/4][j+u/4]^=F[i][j],
                G[i][j+u/4]^=F[i][j],
                G[i+u/2][j+u/4]^=F[i][j],
                G[i+u/4][j+u/2]^=F[i][j];
        int C=0;
        // for(int i=0;i<u;++i,cout<<endl)
        //     for(int j=0;j<u;++j)
        //         cout<<G[i][j],C+=G[i][j];cerr<<C<<endl;
        for(int i=0;i<u;++i)
            for(int j=0;j<u;++j)
                F[i][j]=G[i][j];
    }
    int C=0;
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            if(F[i][j])to.emplace_back(i-n/2+n&n-1,j-n/2+n&n-1);
    for(int i=1;i<n-1;++i)
    {
        for(int j=0;j<n;++j)
            if(b[i-1][j])
            {
                c[i].flip(j),b[i].flip(j),b[i-1].flip(j),b[i].flip(j+n-1&n-1),b[i].flip(j+1&n-1),b[i+1].flip(j);

    // cerr<<"__\n";
    // for(int i=0;i<n;++i,cout<<endl)
    //     for(int j=0;j<n;++j)
    //         cout<<b[i][j];
            }
    }
    cerr<<clock()<<endl;
    for(auto k:to)
    {
        {
            const auto&A=b[n-2];
            auto&B=c[n-2+k.first&n-1];
            B^=(A<<k.second)|(A>>n-k.second);
        }
        {
            const auto&A=b[n-1];
            auto&B=c[n-1+k.first&n-1];
            B^=(A<<k.second)|(A>>n-k.second);
        }
        // for(int i=n-2;i<n;++i)
        //     for(int j=0;j<n;++j)if(b[i][j])
        //         c[i+k.first&n-1].flip(j+k.second&n-1);

    }
    cerr<<clock()<<endl;
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            C+=c[i][j];
    cout<<C<<'\n';
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            if(c[i][j])cout<<i<<" "<<j<<'\n';
    return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 9808kb

input:

3 5 7

output:

64
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
2 0
2 1
2 2
2 3
2 4
2 5
2 6
2 7
3 0
3 1
3 2
3 3
3 4
3 5
3 6
3 7
4 0
4 1
4 2
4 3
4 4
4 5
4 6
4 7
5 0
5 1
5 2
5 3
5 4
5 5
5 6
5 7
6 0
6 1
6 2
6 3
6 4
6 5
6 6
6 7
7 0
7 1
7 2
7 3
7 4
7 5
7 6
7 7

result:

wrong answer 1st lines differ - expected: '105', found: '64'

Test #2:

score: 0
Wrong Answer
time: 1ms
memory: 9744kb

input:

4 4 8

output:

256
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
2 0
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
3 0
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
4 0
4 1
4 2
4 3
...

result:

wrong answer 1st lines differ - expected: '144', found: '256'

Test #3:

score: 0
Wrong Answer
time: 29ms
memory: 12684kb

input:

9 7 53

output:

262144
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
0 18
0 19
0 20
0 21
0 22
0 23
0 24
0 25
0 26
0 27
0 28
0 29
0 30
0 31
0 32
0 33
0 34
0 35
0 36
0 37
0 38
0 39
0 40
0 41
0 42
0 43
0 44
0 45
0 46
0 47
0 48
0 49
0 50
0 51
0 52
0 53
0 54
0 55
0 56
0 57
0 58
0 59
0 6...

result:

wrong answer 1st lines differ - expected: '11271960', found: '262144'

Test #4:

score: 0
Wrong Answer
time: 95ms
memory: 17952kb

input:

10 10 60

output:

1048576
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
0 18
0 19
0 20
0 21
0 22
0 23
0 24
0 25
0 26
0 27
0 28
0 29
0 30
0 31
0 32
0 33
0 34
0 35
0 36
0 37
0 38
0 39
0 40
0 41
0 42
0 43
0 44
0 45
0 46
0 47
0 48
0 49
0 50
0 51
0 52
0 53
0 54
0 55
0 56
0 57
0 58
0 59
0 ...

result:

wrong answer 1st lines differ - expected: '711797984', found: '1048576'

Test #5:

score: 0
Time Limit Exceeded

input:

50 100 100

output:

result:

Test #6:

score: 0
Wrong Answer
time: 2ms
memory: 9976kb

input:

69 69 99

output:

1024
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
0 18
0 19
0 20
0 21
0 22
0 23
0 24
0 25
0 26
0 27
0 28
0 29
0 30
0 31
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
...

result:

wrong answer 1st lines differ - expected: '205514286', found: '1024'

Test #7:

score: 0
Time Limit Exceeded

input:

500 10 3232

output:

result:

Test #8:

score: 0
Wrong Answer
time: 2ms
memory: 9864kb

input:

70 70 4800

output:

4096
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
0 18
0 19
0 20
0 21
0 22
0 23
0 24
0 25
0 26
0 27
0 28
0 29
0 30
0 31
0 32
0 33
0 34
0 35
0 36
0 37
0 38
0 39
0 40
0 41
0 42
0 43
0 44
0 45
0 46
0 47
0 48
0 49
0 50
0 51
0 52
0 53
0 54
0 55
0 56
0 57
0 58
0 59
0 60
...

result:

wrong answer 1st lines differ - expected: '851456413', found: '4096'

Test #9:

score: 0
Wrong Answer
time: 1ms
memory: 9888kb

input:

100 1000 50000

output:

256
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
2 0
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
3 0
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
4 0
4 1
4 2
4 3
...

result:

wrong answer 1st lines differ - expected: '437541409', found: '256'

Test #10:

score: 0
Wrong Answer
time: 783ms
memory: 24216kb

input:

316 316 4238

output:

0

result:

wrong answer 1st lines differ - expected: '753478761', found: '0'

Test #11:

score: 0
Wrong Answer
time: 24ms
memory: 12404kb

input:

201 479 30001

output:

262144
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
0 18
0 19
0 20
0 21
0 22
0 23
0 24
0 25
0 26
0 27
0 28
0 29
0 30
0 31
0 32
0 33
0 34
0 35
0 36
0 37
0 38
0 39
0 40
0 41
0 42
0 43
0 44
0 45
0 46
0 47
0 48
0 49
0 50
0 51
0 52
0 53
0 54
0 55
0 56
0 57
0 58
0 59
0 6...

result:

wrong answer 1st lines differ - expected: '594408179', found: '262144'

Test #12:

score: 0
Wrong Answer
time: 1ms
memory: 7748kb

input:

706 706 706

output:

16
0 0
0 1
0 2
0 3
1 0
1 1
1 2
1 3
2 0
2 1
2 2
2 3
3 0
3 1
3 2
3 3

result:

wrong answer 1st lines differ - expected: '835727049', found: '16'

Test #13:

score: 0
Wrong Answer
time: 3ms
memory: 10132kb

input:

2023 233 2023

output:

16384
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
0 18
0 19
0 20
0 21
0 22
0 23
0 24
0 25
0 26
0 27
0 28
0 29
0 30
0 31
0 32
0 33
0 34
0 35
0 36
0 37
0 38
0 39
0 40
0 41
0 42
0 43
0 44
0 45
0 46
0 47
0 48
0 49
0 50
0 51
0 52
0 53
0 54
0 55
0 56
0 57
0 58
0 59
0 60...

result:

wrong answer 1st lines differ - expected: '801992885', found: '16384'

Test #14:

score: 0
Time Limit Exceeded

input:

402 402 1000

output:

result:

Test #15:

score: 0
Wrong Answer
time: 0ms
memory: 7812kb

input:

707 333 999

output:

64
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
2 0
2 1
2 2
2 3
2 4
2 5
2 6
2 7
3 0
3 1
3 2
3 3
3 4
3 5
3 6
3 7
4 0
4 1
4 2
4 3
4 4
4 5
4 6
4 7
5 0
5 1
5 2
5 3
5 4
5 5
5 6
5 7
6 0
6 1
6 2
6 3
6 4
6 5
6 6
6 7
7 0
7 1
7 2
7 3
7 4
7 5
7 6
7 7

result:

wrong answer 1st lines differ - expected: '732112489', found: '64'

Test #16:

score: 0
Time Limit Exceeded

input:

600 600 18000

output:

result:

Test #17:

score: 0
Wrong Answer
time: 0ms
memory: 7924kb

input:

389 1047 40001

output:

1024
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
0 18
0 19
0 20
0 21
0 22
0 23
0 24
0 25
0 26
0 27
0 28
0 29
0 30
0 31
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
...

result:

wrong answer 1st lines differ - expected: '186903191', found: '1024'

Test #18:

score: 0
Wrong Answer
time: 1ms
memory: 9920kb

input:

707 707 42837

output:

64
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
2 0
2 1
2 2
2 3
2 4
2 5
2 6
2 7
3 0
3 1
3 2
3 3
3 4
3 5
3 6
3 7
4 0
4 1
4 2
4 3
4 4
4 5
4 6
4 7
5 0
5 1
5 2
5 3
5 4
5 5
5 6
5 7
6 0
6 1
6 2
6 3
6 4
6 5
6 6
6 7
7 0
7 1
7 2
7 3
7 4
7 5
7 6
7 7

result:

wrong answer 1st lines differ - expected: '468460621', found: '64'

Test #19:

score: 0
Wrong Answer
time: 1ms
memory: 7840kb

input:

100 5000 32346

output:

256
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
2 0
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
3 0
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
4 0
4 1
4 2
4 3
...

result:

wrong answer 1st lines differ - expected: '460579847', found: '256'

Test #20:

score: 0
Time Limit Exceeded

input:

501 501 251001

output:

result:
English 繁體中文 简体中文

Server Time: 2024-12-05 08:34:24 | OpenSource Project