QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#89100 | #992. Number of Colorful Matchings | vme50 | AC ✓ | 30ms | 3992kb | C++14 | 1.4kb | 2023-03-18 22:54:13 | 2023-03-18 22:54:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define N 305
int n;bool a[N][N],b[N][N],z[N][N];char tmp[N];
void eliminate()
{
for(int i=1,t;i<=n;++i)
{
t=0;for(int j=1;j<=n;++j) if(a[j][i]) t=j;if(!t) continue;
for(int j=1;j<=n;++j) swap(a[i][j],a[t][j]),swap(b[i][j],b[t][j]);
for(int j=1;j<=n;++j) if(i!=j && a[j][i])
for(int k=1;k<=n;++k) a[j][k]^=a[i][k],b[j][k]^=b[i][k];
for(int j=i+1;j<=n;++j) if(a[i][j])
for(int k=1;k<=n;++k) a[k][j]^=a[k][i],b[k][j]^=b[k][i];
}
for(int i=2,t;i<=n;++i)
{
t=0;for(int j=i;j<=n;++j) if(b[j][i-1] && (!t || !a[j][j])) t=j;
if(!t) continue;swap(a[i][i],a[t][t]);
for(int j=i-1;j<=n;++j) swap(b[i][j],b[t][j]);
for(int j=1;j<=n;++j) swap(b[j][i],b[j][t]);
for(int j=i+1;j<=n;++j) if(b[j][i-1])
{
for(int k=i-1;k<=n;++k) b[j][k]^=b[i][k];
if(a[i][i]) for(int k=1;k<=n;++k) b[k][i]^=b[k][j];
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{scanf("%s",tmp+1);for(int j=1;j<=n;++j) a[i][j]=tmp[j]-48;}
for(int i=1;i<=n;++i)
{scanf("%s",tmp+1);for(int j=1;j<=n;++j) b[i][j]=tmp[j]-48;}
eliminate();z[0][0]=1;
for(int i=1;i<=n;++i)
{
for(int j=0;j<i;++j)
{
if(a[j+1][i]) for(int k=0;k<i;++k) z[i][k+1]^=z[j][k];
if(b[j+1][i]) for(int k=0;k<i;++k) z[i][k]^=z[j][k];
}
for(int j=0;j<i;++j) if(!b[i+1][i])
for(int k=0;k<i;++k) z[j][k]=0;
}for(int i=0;i<=n;++i) printf("%d\n",z[n][i]);return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3556kb
input:
2 11 10 00 11
output:
0 0 1
result:
ok 3 tokens
Test #2:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
10 0100110000 0000010111 0111000111 1000101100 1101000001 1111110000 1001001110 0000000011 0001000010 0100100110 1100010101 0001000001 0001001010 0011100111 0010101111 1001011011 1001100111 0111101001 0010100010 0001111011
output:
0 0 0 1 1 1 1 1 0 0 1
result:
ok 11 tokens
Test #3:
score: 0
Accepted
time: 2ms
memory: 3616kb
input:
18 001100000000010111 011100011110001011 001101000001111111 000010010011100000 000011000100001001 001001101100010101 000100000100010010 100011100111001010 111110010110111001 100111011110100100 101000100001111011 110000100101011111 101011001000000111 110001011110010101 110010011111001110 001001011100...
output:
0 0 0 1 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0
result:
ok 19 tokens
Test #4:
score: 0
Accepted
time: 2ms
memory: 3512kb
input:
18 110000000001011101 110001111000101100 110100000111111100 001001001110000000 001100010000100100 100110110001010100 010000010001001010 001110011100101011 111001011011100110 011101111010010010 100010000111101111 000010010101111110 101100100000011111 000101111001010111 001001111100111000 100101110010...
output:
0 0 0 0 1 0 1 1 1 0 1 1 0 0 1 0 1 1 0
result:
ok 19 tokens
Test #5:
score: 0
Accepted
time: 29ms
memory: 3764kb
input:
300 00000000010111011100011110001011001101000001111111000010010011100000000011000100001001001001101100010101000100000100010010100011100111001010111110010110111001100111011110100100101000100001111011110000100101011111101011001000000111110001011110010101110010011111001110001001011100100010010000000000...
output:
0 0 0 0 0 1 1 1 0 1 1 1 0 0 0 1 1 0 1 0 0 1 1 0 0 0 0 1 0 0 0 1 1 0 1 0 1 0 1 0 1 1 1 0 0 1 0 0 1 1 1 1 0 0 0 1 1 0 1 1 1 0 0 1 1 1 1 0 1 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 1 0 0 1 1 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 1 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 1 0 1 1 1 0 1 1 0 0 1 0 1 1 ...
result:
ok 301 tokens
Test #6:
score: 0
Accepted
time: 26ms
memory: 3992kb
input:
300 00000001011101110001111000101100110100000111111100001001001110000000001100010000100100100110110001010100010000010001001010001110011100101011111001011011100110011101111010010010100010000111101111000010010101111110101100100000011111000101111001010111001001111100111000100101110010001001000000000001...
output:
0 0 0 1 0 1 1 0 0 0 0 1 1 1 0 0 1 0 0 0 0 1 0 1 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 1 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0 1 1 0 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 0 1 1 1 1 1 1 0 1 0 0 1 0 0 1 0 1 0 0 0 0 1 1 0 1 1 0 0 0 1 1 1 0 1 1 0 1 0 1 0 0 1 1 1 0 0 1 0 1 0 0 1 0 1 1 1 1 0 1 1 0 1 0 1 ...
result:
ok 301 tokens
Test #7:
score: 0
Accepted
time: 30ms
memory: 3988kb
input:
300 00000101110111000111100010110011010000011111110000100100111000000000110001000010010010011011000101010001000001000100101000111001110010101111100101101110011001110111101001001010001000011110111100001001010111111010110010000001111100010111100101011100100111110011100010010111001000100100000000000111...
output:
0 0 0 0 0 1 1 1 1 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 0 1 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 1 1 0 1 0 1 0 1 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 0 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 0 0 1 0 1 1 1 ...
result:
ok 301 tokens
Test #8:
score: 0
Accepted
time: 2ms
memory: 3876kb
input:
200 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 201 tokens
Test #9:
score: 0
Accepted
time: 2ms
memory: 3720kb
input:
230 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000...
output:
0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 231 tokens
Test #10:
score: 0
Accepted
time: 6ms
memory: 3828kb
input:
270 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000...
output:
0 0 0 1 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 271 tokens
Test #11:
score: 0
Accepted
time: 2ms
memory: 3776kb
input:
300 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 301 tokens
Test #12:
score: 0
Accepted
time: 2ms
memory: 3540kb
input:
50 11000111100010110011010000011111110000100100111000 00000011000100001001001001101100010101000100000100 01001010001110011100101011111001011011100110011101 11101001001010001000011110111100001001010111111010 11001000000111110001011110010101110010011111001110 001001011100100010010000000000011101110101...
output:
0 1 1 1 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 0 0 1 0 0 0 1 1 1 0 0 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1
result:
ok 51 tokens
Test #13:
score: 0
Accepted
time: 2ms
memory: 3800kb
input:
80 00011110001011001101000001111111000010010011100000000011000100001001001001101100 01010100010000010001001010001110011100101011111001011011100110011101111010010010 10001000011110111100001001010111111010110010000001111100010111100101011100100111 110011100010010111001000100100000000000111011101011011...
output:
0 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1 1 0 1 1 1 0 0 0 1 1 1 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 0 0 0 0 0 1 0 0 1 0 1 1 0 0
result:
ok 81 tokens
Test #14:
score: 0
Accepted
time: 3ms
memory: 3836kb
input:
120 011110001011001101000001111111000010010011100000000011000100001001001001101100010101000100000100010010100011100111001010 111110010110111001100111011110100100101000100001111011110000100101011111101011001000000111110001011110010101110010011111 001110001001011100100010010000000000011101110101101110...
output:
0 1 0 0 1 0 1 0 0 1 1 0 0 0 1 1 0 1 0 0 0 0 0 1 1 1 0 1 0 0 0 0 1 1 0 1 1 0 0 1 1 1 0 1 1 1 0 0 0 1 0 1 0 1 1 1 1 1 0 1 0 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 1 1 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0
result:
ok 121 tokens
Test #15:
score: 0
Accepted
time: 3ms
memory: 3660kb
input:
180 111000101100110100000111111100001001001110000000001100010000100100100110110001010100010000010001001010001110011100101011111001011011100110011101111010010010100010000111101111000010 0101011111101011001000000111110001011110010101110010011111001110001001011100100010010000000000011101110101101110100...
output:
0 1 0 0 1 1 1 1 0 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 1 1 1 1 0 1 1 1 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 0 1 0 1 1 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 1 1 1 0 1 1 1 1 0 0 1 0 1 1 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 ...
result:
ok 181 tokens
Test #16:
score: 0
Accepted
time: 11ms
memory: 3740kb
input:
220 1000101100110100000111111100001001001110000000001100010000100100100110110001010100010000010001001010001110011100101011111001011011100110011101111010010010100010000111101111000010010101111110101100100000011111000101111001 010111001001111100111000100101110010001001000000000001110111010110111010011...
output:
1 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 1 1 0 0 1 0 1 0 1 1 0 0 1 1 0 1 1 1 0 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 0 1 0 1 1 0 1 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 1 1 0 1 1 1 1 1 1 1 0 1 0 1 0 0 1 1 0 1 0 ...
result:
ok 221 tokens
Test #17:
score: 0
Accepted
time: 17ms
memory: 3792kb
input:
250 0010110011010000011111110000100100111000000000110001000010010010011011000101010001000001000100101000111001110010101111100101101110011001110111101001001010001000011110111100001001010111111010110010000001111100010111100101011100100111110011100010010111 001000100100000000000111011101011011101001111...
output:
0 1 1 1 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 1 1 0 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 1 0 1 1 1 1 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 1 0 1 1 0 1 1 0 0 1 1 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 1 1 0 1 1 1 1 0 1 1 0 0 1 1 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 0 1 0 ...
result:
ok 251 tokens
Test #18:
score: 0
Accepted
time: 17ms
memory: 3976kb
input:
270 101100110100000111111100001001001110000000001100010000100100100110110001010100010000010001001010001110011100101011111001011011100110011101111010010010100010000111101111000010010101111110101100100000011111000101111001010111001001111100111000100101110010001001000000000001 1101110101101110100111111...
output:
0 1 0 0 1 1 1 0 0 1 0 1 0 1 1 0 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 0 0 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 1 0 1 0 0 1 0 0 0 1 1 0 0 1 1 0 1 1 1 1 0 1 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 1 1 0 0 0 0 1 0 0 ...
result:
ok 271 tokens
Test #19:
score: 0
Accepted
time: 28ms
memory: 3828kb
input:
300 11001101000001111111000010010011100000000011000100001001001001101100010101000100000100010010100011100111001010111110010110111001100111011110100100101000100001111011110000100101011111101011001000000111110001011110010101110010011111001110001001011100100010010000000000011101110101101110100111111110...
output:
0 0 0 0 1 0 1 0 0 1 1 1 1 0 0 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 1 1 1 0 0 1 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1 0 1 ...
result:
ok 301 tokens
Test #20:
score: 0
Accepted
time: 24ms
memory: 3812kb
input:
300 00110100000111111100001001001110000000001100010000100100100110110001010100010000010001001010001110011100101011111001011011100110011101111010010010100010000111101111000010010101111110101100100000011111000101111001010111001001111100111000100101110010001001000000000001110111010110111010011111111010...
output:
1 1 0 1 1 0 1 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 1 1 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 ...
result:
ok 301 tokens
Test #21:
score: 0
Accepted
time: 28ms
memory: 3788kb
input:
300 11010000011111110000100100111000000000110001000010010010011011000101010001000001000100101000111001110010101111100101101110011001110111101001001010001000011110111100001001010111111010110010000001111100010111100101011100100111110011100010010111001000100100000000000111011101011011101001111111101001...
output:
0 1 0 1 0 1 1 0 1 1 0 0 0 0 1 1 1 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 1 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 1 0 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 0 1 0 1 0 0 1 0 1 1 1 1 1 0 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 ...
result:
ok 301 tokens