QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#842856#9968. Just Zerosucup-team3586#TL 828ms104708kbC++231.9kb2025-01-04 15:23:052025-01-04 15:23:06

Judging History

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

  • [2025-01-04 15:23:06]
  • 评测
  • 测评结果:TL
  • 用时:828ms
  • 内存:104708kb
  • [2025-01-04 15:23:05]
  • 提交

answer

#include<bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
// #define int long long
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
const int p=998244353;
int qp(int x,int y)
{
	int res=1;
	for(int t=x; y; y>>=1,t=1ll*t*t%p)
		if(y&1) res=1ll*res*t%p;
	return res;
}
char s[8][100003];
int a[256][100003];
int b[100003];
signed main()
{
	int n=read(),m=read(),T=read();
	for(int i=0; i<n; ++i) scanf("%s",s[i]+1);
	int N=1<<n;
	int base=0;
	for(int k=0; k<N; ++k)
	{
		for(int i=0; i<n; ++i)
			for(int j=1; j<=m; ++j)
				a[k][j]+=((s[i][j]=='1')^((k>>i)&1));
		for(int j=1; j<=m; ++j)
			b[k]+=min(a[k][j],n+1-a[k][j]);
	}
	auto calc=[&]()
	{
		int ans=1e9;
		for(int i=0; i<N; ++i)
			ans=min(ans,__builtin_popcount(i^base)+b[i]);
		printf("%d\n",ans);
		return ;
	};
	calc();
	while(T--)
	{
		char c=getchar();
		while(!isupper(c)) c=getchar();
		if(c=='R')
		{
			base^=(1<<(read()-1));
		}
		else if(c=='K')
		{
			int j=read();
			for(int i=0; i<n; ++i)
			s[i][j]^=1;
			for(int k=0; k<N; ++k)
			{
				b[k]-=min(a[k][j],n+1-a[k][j]);
				for(int i=0; i<n; ++i)
					a[k][j]-=((s[i][j]=='0')^((k>>i)&1)),
					
					a[k][j]+=((s[i][j]=='1')^((k>>i)&1));
				b[k]+=min(a[k][j],n+1-a[k][j]);
				// if(k==0) printf("qwq %d\n",b[k]);
			}
		}
		else
		{
			int i=read()-1,j=read();
			s[i][j]^=1;
			for(int k=0; k<N; ++k)
			{
				b[k]-=min(a[k][j],n+1-a[k][j]);
					a[k][j]-=((s[i][j]=='0')^((k>>i)&1)),
					
					a[k][j]+=((s[i][j]=='1')^((k>>i)&1));
				b[k]+=min(a[k][j],n+1-a[k][j]);
				// if(k==0) printf("qwq %d\n",b[k]);
			}
		}
		calc();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 7860kb

input:

3 4 6
1010
1101
0010
R 2
P 3 1
K 2
P 2 1
K 4
P 3 4

output:

3
2
3
4
3
3
4

result:

ok 7 numbers

Test #2:

score: 0
Accepted
time: 3ms
memory: 6060kb

input:

3 4 100000
0100
0011
0011
R 3
K 1
R 2
K 4
R 3
K 2
P 1 1
K 1
R 1
P 1 4
K 4
K 1
K 4
R 3
K 2
K 2
R 1
K 1
K 4
P 3 2
P 2 1
K 1
R 1
P 3 1
R 3
K 3
P 3 2
P 1 3
K 1
R 1
P 1 1
R 1
P 2 1
R 3
P 3 1
R 2
K 2
R 1
R 1
R 3
P 1 3
R 3
K 3
R 2
R 1
P 3 4
K 1
K 1
P 1 4
R 3
K 1
P 1 2
R 1
K 3
P 2 2
R 1
P 1 1
K 4
R 2
P 3 4
...

output:

4
4
3
2
3
4
3
2
3
3
4
4
3
4
3
4
3
2
3
2
3
4
3
4
4
5
5
5
4
3
4
4
4
5
4
3
4
4
3
4
3
3
4
5
4
4
5
4
5
4
4
4
4
5
5
4
4
3
4
5
4
3
4
4
5
4
5
4
5
4
4
5
5
4
5
5
4
4
4
3
4
3
2
3
4
4
3
4
4
3
3
4
3
4
4
3
4
3
2
3
2
3
2
3
4
3
2
3
4
4
3
4
5
5
5
5
4
4
4
5
4
4
4
5
5
5
4
3
4
3
4
4
5
4
5
5
5
4
3
4
4
5
4
5
4
5
4
3
4
4
...

result:

ok 100001 numbers

Test #3:

score: 0
Accepted
time: 13ms
memory: 12216kb

input:

4 3 100000
110
110
010
000
K 2
K 3
K 2
R 4
P 3 3
K 3
K 2
R 4
R 2
R 1
P 3 2
R 3
K 1
K 1
R 1
K 3
P 1 3
R 2
K 2
K 3
R 3
P 4 1
K 2
P 1 1
R 3
R 1
R 3
K 3
K 1
K 3
R 3
R 1
K 1
P 2 2
P 2 3
K 2
K 3
K 3
K 3
K 3
P 2 2
R 3
R 4
R 1
P 4 1
P 2 2
K 1
K 1
R 3
K 2
R 4
K 2
R 1
R 4
R 4
K 1
P 4 2
R 3
K 3
R 2
R 1
K 1
K 1...

output:

4
3
4
5
5
5
5
4
4
5
4
3
4
4
4
4
4
5
4
5
5
4
5
4
5
4
3
4
5
4
3
2
3
4
4
5
4
5
4
5
4
5
5
4
5
4
5
4
5
5
5
5
4
5
6
5
4
5
5
4
5
4
5
4
3
4
5
5
4
3
4
5
5
5
4
5
4
5
4
4
4
3
4
5
4
3
4
4
4
3
4
4
4
5
4
4
3
4
4
5
4
5
4
5
4
5
4
4
5
4
5
5
4
3
2
3
4
5
4
4
4
5
4
3
4
4
4
3
4
3
4
4
3
3
4
4
3
2
3
2
3
3
3
4
3
4
5
4
5
5
...

result:

ok 100001 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 3720kb

input:

1 1 10000
1
P 1 1
R 1
P 1 1
K 1
P 1 1
P 1 1
R 1
K 1
P 1 1
K 1
K 1
P 1 1
K 1
K 1
R 1
R 1
K 1
K 1
K 1
R 1
P 1 1
K 1
P 1 1
R 1
R 1
K 1
P 1 1
K 1
K 1
K 1
K 1
K 1
K 1
K 1
R 1
P 1 1
P 1 1
R 1
K 1
P 1 1
R 1
R 1
R 1
K 1
P 1 1
P 1 1
P 1 1
R 1
R 1
P 1 1
R 1
K 1
R 1
P 1 1
R 1
K 1
R 1
P 1 1
R 1
P 1 1
K 1
R 1
R ...

output:

1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
...

result:

ok 10001 numbers

Test #5:

score: 0
Accepted
time: 8ms
memory: 5812kb

input:

2 2 100000
11
01
K 1
R 1
K 2
R 1
K 1
P 2 2
K 2
R 2
P 2 1
K 2
R 1
R 1
K 1
K 1
R 2
P 1 2
P 2 2
K 2
R 2
K 1
R 2
P 2 1
R 1
K 2
P 1 1
P 1 1
P 1 1
P 2 2
K 1
R 2
P 2 2
P 2 2
P 1 2
P 2 1
R 2
P 2 2
P 2 1
K 2
K 2
P 2 2
P 2 1
R 1
R 1
K 2
K 2
P 2 1
R 1
P 1 2
R 2
P 1 1
R 2
R 1
P 2 1
P 1 1
K 1
K 2
R 1
P 2 1
R 1
K...

output:

2
2
2
2
1
1
2
1
2
2
1
1
1
1
1
2
2
2
2
1
1
1
1
2
1
1
1
1
1
2
1
2
1
2
1
2
2
1
2
1
2
2
1
2
1
2
2
1
1
2
2
2
1
1
2
1
1
1
1
2
1
0
1
2
1
2
1
0
1
2
1
2
1
2
2
2
2
2
2
1
2
1
1
1
1
2
1
2
1
1
1
2
2
2
1
1
1
2
2
1
1
1
2
2
1
2
1
1
2
1
2
1
1
1
0
1
1
1
1
2
2
1
2
1
2
2
1
0
1
2
1
2
1
2
1
0
1
0
1
2
1
2
1
0
1
1
1
1
1
1
...

result:

ok 100001 numbers

Test #6:

score: 0
Accepted
time: 0ms
memory: 104104kb

input:

8 100 100
1011100111011111110000100100100101000100111100011000001000101011001101001011010100110010110100010110
1001100100100101011101110000100001100001010100111011100111101000110011000010010001000010001101000001
0111000100001001100001111000111110100111100000010111100110110010110100000010011011100000...

output:

302
303
304
305
305
304
305
304
303
302
303
302
301
300
301
302
301
302
301
300
299
298
299
300
299
298
299
300
299
300
301
302
302
301
300
299
300
301
302
301
302
303
302
303
302
301
301
300
299
298
297
298
299
298
298
297
298
297
296
295
296
295
294
294
295
296
295
296
297
298
299
299
300
301
302
...

result:

ok 101 numbers

Test #7:

score: 0
Accepted
time: 0ms
memory: 57108kb

input:

7 100 100
0110101100110100101101011011110110011011111111001001111111111110011000000110010000110001001100000000
1011011110010100111101010001101000100110011111110111000110111110000101000010001001110110101101100101
0010010101110110010111010010000111000101110101111110110010110011100001101001010001101011...

output:

275
275
275
274
273
274
274
275
274
274
273
274
275
275
275
275
275
275
274
273
274
273
272
271
270
269
270
271
272
271
272
271
270
269
270
269
268
267
268
269
270
271
270
269
268
269
270
269
270
271
272
273
274
273
272
271
270
269
268
267
268
267
268
267
268
267
268
269
270
269
268
269
268
267
266
...

result:

ok 101 numbers

Test #8:

score: 0
Accepted
time: 0ms
memory: 28628kb

input:

6 100 100
1010111111000000010001111010011000101111101101010010001010100000000100001011010100001001101110110111
1100110100111000100000011001011111001010000011011011000011010100101110101110110000101001010110001011
0101000000000111000100010011100001001010011001010100110111010111111101001101010011101111...

output:

224
225
226
225
224
224
225
226
225
226
225
226
225
226
225
226
225
226
226
226
226
226
225
226
227
227
226
227
227
228
227
228
229
228
227
228
229
229
228
228
227
228
227
228
227
226
225
224
223
223
223
224
225
225
224
225
225
225
224
225
226
227
226
225
226
226
227
226
226
227
226
226
227
228
229
...

result:

ok 101 numbers

Test #9:

score: 0
Accepted
time: 8ms
memory: 4020kb

input:

1 100 100000
0011100001111101100101010100101011111101000011001110000100000111100011000010010011011000010011100100
K 90
R 1
R 1
R 1
K 51
K 38
K 47
R 1
R 1
P 1 96
K 56
K 19
K 20
R 1
K 52
P 1 90
P 1 66
P 1 35
R 1
P 1 57
R 1
R 1
P 1 56
R 1
K 29
K 96
R 1
R 1
R 1
R 1
K 40
K 68
P 1 9
P 1 92
P 1 78
R 1
K 30...

output:

46
45
46
45
46
45
44
45
44
45
46
45
46
45
44
45
46
47
46
47
48
47
48
49
48
47
46
47
46
47
46
45
46
47
48
47
48
49
48
49
50
50
49
50
50
50
50
50
49
50
49
50
49
50
50
50
49
50
50
49
48
49
50
49
48
49
48
49
48
47
48
49
48
49
48
47
48
47
46
47
46
45
46
45
46
45
46
47
48
47
46
47
48
47
48
47
46
47
48
49
...

result:

ok 100001 numbers

Test #10:

score: 0
Accepted
time: 9ms
memory: 6056kb

input:

2 100 100000
1010001101110111101111110111011110011110111110111110111010000110011111101100111001010011110001101110
0110010111101101111010000001001011101100110101000101100001011111100110010110010000110011001011000110
K 50
R 1
K 22
R 2
P 1 19
K 7
R 2
R 1
P 2 95
P 1 1
R 2
K 96
R 1
P 2 34
K 49
R 2
P 2 21...

output:

66
66
65
66
67
67
68
67
68
69
70
71
70
69
69
69
70
69
70
70
69
69
70
71
71
71
71
71
70
70
69
70
71
71
71
70
69
68
68
69
68
69
68
69
69
70
69
69
69
68
68
69
70
70
71
72
71
71
72
71
72
71
70
70
69
68
67
67
68
68
68
69
68
68
67
67
68
69
70
70
69
68
68
69
70
69
70
70
71
72
72
71
71
72
72
71
70
71
71
72
...

result:

ok 100001 numbers

Test #11:

score: 0
Accepted
time: 183ms
memory: 102200kb

input:

8 100 100000
1011011101111011000001001110011100111000101001100010001110010100001010010110111001111010111100111100
0111101001110111101001010011011011001010100100111111110111110001010010011111011010010100001110111110
1111110111110010110110111110101111001001000011000000000011111011000100001011011101110...

output:

306
307
306
305
305
306
305
304
303
302
303
303
302
303
302
303
303
304
303
302
301
301
300
301
301
301
302
303
304
303
304
305
306
306
307
306
307
306
307
308
307
306
305
306
305
304
303
303
302
303
303
302
301
302
302
303
302
301
302
301
302
301
302
301
301
302
303
302
303
302
302
303
302
302
302
...

result:

ok 100001 numbers

Test #12:

score: 0
Accepted
time: 827ms
memory: 104536kb

input:

8 100000 100000
01101011010110010101001010111010111001101100100101001101001011000111110101011010010011100000001001011101010011110001111100000001010100011000010001000101100100101010001011111111111101101111110100010010100010100010110101101010000011010100100100100111110001000111100101110100111001100110...

output:

322545
322546
322545
322545
322544
322543
322544
322543
322543
322542
322542
322543
322542
322541
322541
322541
322540
322541
322542
322541
322541
322542
322542
322543
322544
322545
322544
322543
322542
322542
322541
322540
322541
322542
322543
322544
322543
322544
322544
322543
322542
322543
322542...

result:

ok 100001 numbers

Test #13:

score: 0
Accepted
time: 828ms
memory: 104536kb

input:

8 99999 100000
001011011110001110100010100000010011010011000111100101101011100101001011000010000001010001110101110101010011100110011111100001010000001010110010010000010100100110111000100100111011000010101111101110000100000111110111101111000001000000010111000111111010011101110001010111010010100010110...

output:

326724
326724
326724
326723
326722
326721
326720
326721
326722
326721
326721
326722
326723
326722
326722
326722
326721
326720
326721
326722
326722
326721
326720
326719
326720
326719
326720
326719
326719
326720
326720
326720
326719
326720
326721
326722
326721
326721
326720
326719
326718
326717
326718...

result:

ok 100001 numbers

Test #14:

score: 0
Accepted
time: 180ms
memory: 102368kb

input:

8 1 100000
1
0
1
1
1
0
0
0
K 1
R 2
R 3
K 1
P 7 1
K 1
R 6
R 7
R 8
K 1
K 1
K 1
K 1
P 1 1
P 1 1
P 8 1
K 1
K 1
P 8 1
P 1 1
K 1
K 1
R 2
R 4
K 1
K 1
P 7 1
P 8 1
P 3 1
R 5
P 5 1
K 1
R 3
P 3 1
R 6
R 5
R 3
K 1
P 5 1
P 7 1
P 2 1
R 6
R 6
P 4 1
R 5
R 7
R 4
R 4
K 1
R 7
P 3 1
K 1
K 1
K 1
R 6
P 8 1
P 5 1
K 1
R 8
R...

output:

4
4
3
4
4
4
3
2
3
2
3
2
3
2
3
2
3
4
3
2
3
4
3
4
4
3
4
4
4
4
4
4
4
3
4
3
2
1
2
3
2
3
4
3
4
3
4
3
4
3
2
3
4
3
4
4
3
2
3
4
4
4
3
4
4
4
3
4
4
3
4
4
4
3
4
3
4
4
4
3
2
3
2
1
2
3
2
3
2
3
2
3
4
4
4
3
4
3
2
3
4
4
3
4
4
3
2
3
4
4
4
4
4
4
4
3
4
4
4
4
3
4
3
4
4
4
4
4
4
4
3
2
3
4
3
4
3
4
4
4
4
4
3
4
4
4
4
4
4
3
...

result:

ok 100001 numbers

Test #15:

score: 0
Accepted
time: 30ms
memory: 52980kb

input:

7 5 33232
11010
00110
00111
01000
00010
11011
11110
R 2
P 7 1
R 6
K 2
P 4 5
P 1 5
K 3
P 7 5
P 2 5
K 1
K 4
P 6 1
P 3 4
P 6 4
R 4
K 5
P 6 1
K 1
R 2
R 6
P 7 4
R 1
P 6 5
K 1
R 1
R 3
R 5
K 1
R 1
K 1
P 3 4
K 3
R 5
P 5 5
P 4 2
K 5
R 1
P 2 4
P 1 5
K 5
R 5
P 4 4
R 2
P 2 2
K 2
P 6 5
R 4
P 2 1
P 7 1
R 6
R 3
P ...

output:

14
13
14
13
12
13
12
11
12
13
14
13
14
15
14
13
14
13
12
11
12
13
12
11
12
13
12
13
14
13
14
13
12
13
12
13
12
11
10
9
10
9
10
9
10
11
12
13
14
13
12
11
10
11
12
11
12
11
12
13
14
13
14
13
14
13
12
13
14
13
14
13
14
13
12
13
14
13
14
13
12
13
14
13
12
11
12
13
12
11
12
11
12
13
12
11
12
11
12
11
12
...

result:

ok 33233 numbers

Test #16:

score: 0
Accepted
time: 627ms
memory: 104572kb

input:

8 100000 100000
10110100101110110111010110010001100100101000000001011101000011100011010100110000110111100001100100000000111011100000010010011101100101101010110000001001110101100000000101101100110110100100001101010001001100110011001011010010110101111001001000010111110000011111101100101101110001001111...

output:

322504
322504
322504
322503
322503
322502
322501
322500
322499
322498
322499
322500
322499
322500
322500
322501
322501
322502
322502
322501
322502
322503
322504
322503
322504
322505
322506
322507
322508
322507
322506
322507
322508
322508
322508
322509
322510
322509
322510
322511
322510
322509
322510...

result:

ok 100001 numbers

Test #17:

score: 0
Accepted
time: 232ms
memory: 104708kb

input:

8 100000 100000
00011111100111101010010101001001000110100001011011100111001010100111001001111100101010011111010000100101110001101100011101000001011101111100110110010101001011100000000110101100010110010111000001010111000001111111000100011001100111111100011000110011110100101101000100100010100110111001...

output:

322504
322503
322502
322503
322504
322503
322504
322505
322504
322503
322504
322505
322504
322503
322502
322501
322502
322501
322502
322503
322502
322501
322502
322501
322502
322501
322502
322501
322502
322503
322502
322501
322502
322503
322504
322503
322502
322503
322502
322503
322502
322503
322504...

result:

ok 100001 numbers

Test #18:

score: -100
Time Limit Exceeded

input:

8 100000 100000
00001011001110110000101101111011101000000100000001101011001110000111111000000101100110110001100101101011100101000101101001001011101111000110010100111011100011101011101001100100100110101010100110011011101111001011101111111110011000001111010110001111010100110101100001111100101101110110...

output:

322528
322527
322527
322527
322526
322526
322526
322525
322524
322523
322522
322521
322520
322521
322521
322520
322519
322519
322519
322518
322519
322520
322520
322519
322518
322519
322519
322518
322517
322518
322519
322518
322518
322517
322517
322516
322517
322518
322517
322518
322517
322516
322515...

result: