QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#860229 | #9968. Just Zeros | Judgelight | WA | 39ms | 8752kb | C++14 | 1.9kb | 2025-01-18 11:26:49 | 2025-01-18 11:26:57 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define eb emplace_back
#define mk make_pair
#define N 100009
using namespace std;
int h,w,q,qp[N],qi[N],qj[N],ans[N],res[9][9][2],cnt[9],hh[9],d[9][N];char c[9][N];
void mdf(int x,int y){
int pre=d[x][y]^hh[x],sum=0;for(int j=0;j<h;j++)if(d[j][y]^hh[j])sum++;
for(int j=0;j<h;j++){
res[j][sum][d[j][y]^hh[j]]--;
}
cnt[sum]--,cnt[sum-pre+(pre^1)]++,d[x][y]^=1;
for(int j=0;j<h;j++){
res[j][sum][d[j][y]^hh[j]]++;
}
}
signed main(){
scanf("%d%d%d",&h,&w,&q);
for(int i=0;i<h;i++)scanf("%s",c[i]);
memset(ans,0x3f,sizeof(ans));
char ch[2];for(int i=1;i<=q;i++){
scanf("%s",ch);
if(ch[0]=='P')qp[i]=0,scanf("%d%d",&qi[i],&qj[i]),qi[i]--,qj[i]--;
else if(ch[0]=='R')qp[i]=1,scanf("%d",&qi[i]),qi[i]--;
else qp[i]=2,scanf("%d",&qj[i]),qj[i]--;
}
for(int s=0;s<(1<<h);s++){
memset(res,0,sizeof(res));memset(cnt,0,sizeof(cnt));memset(hh,0,sizeof(hh));
for(int i=0;i<=h;i++)for(int j=0;j<w;j++)d[i][j]=((s>>i)&1)^(c[i][j]-'0');
for(int j=0;j<w;j++){
int dt=0;
for(int i=0;i<h;i++){
int val=d[i][j];
dt+=val;
}
cnt[dt]++;
for(int i=0;i<h;i++){
int val=d[i][j];
res[i][dt][val]++;
}
}
int _1=0;for(int i=0;i<h;i++)if((s>>i)&1)_1++;
int nw=0;for(int j=0;j<=h;j++)nw+=cnt[j]*min(j,h-j+1);
ans[0]=min(ans[0],nw+_1);
for(int i=1;i<=q;i++){
if(qp[i]==0){
mdf(qi[i],qj[i]);
}
else if(qp[i]==1){
int x=qi[i],res1[9][2];memset(res1,0,sizeof(res1));memset(cnt,0,sizeof(cnt));
hh[x]^=1;
for(int j=0;j<8;j++)res1[j+1][1]+=res[x][j][0];
for(int j=1;j<=8;j++)res1[j-1][0]+=res[x][j][1];
for(int j=0;j<=8;j++)res[x][j][0]=res1[j][0],res[x][j][1]=res1[j][1],cnt[j]+=res[x][j][0]+res[x][j][1];
}
else{
for(int j=0;j<h;j++)mdf(j,qj[i]);
}
int nw=0;for(int j=0;j<=h;j++)nw+=cnt[j]*min(j,h-j+1);
ans[i]=min(ans[i],nw+_1);
}
}
for(int i=0;i<=q;i++)printf("%d\n",ans[i]);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 8036kb
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: -100
Wrong Answer
time: 39ms
memory: 8752kb
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 2 2 1 2 -2 -1 -2 -1 -2 -3 -2 -3 -4 -5 -4 -5 -4 -5 -3 -4 -5 -6 -7 -6 -6 -6 -7 -4 -5 -6 -7 -7 -8 -7 -4 -9 -10 -6 -5 0 -10 -9 -8 -9 -10 -12 -11 -12 -7 -6 -7 -10 -11 -12 -13 -12 -10 -8 -10 -11 -10 0 0 0 -1 -13 -12 -12 -11 -12 -11 -10 -9 -16 -17 -16 -20 -19 -18 -12 -18 -19 -18 -17 -16 -15 -3 -2...
result:
wrong answer 6th numbers differ - expected: '4', found: '2'