QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#842856 | #9968. Just Zeros | ucup-team3586# | TL | 828ms | 104708kb | C++23 | 1.9kb | 2025-01-04 15:23:05 | 2025-01-04 15:23:06 |
Judging History
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...