QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#89100#992. Number of Colorful Matchingsvme50AC ✓30ms3992kbC++141.4kb2023-03-18 22:54:132023-03-18 22:54:17

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-18 22:54:17]
  • 评测
  • 测评结果:AC
  • 用时:30ms
  • 内存:3992kb
  • [2023-03-18 22:54:13]
  • 提交

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