QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#860229#9968. Just ZerosJudgelightWA 39ms8752kbC++141.9kb2025-01-18 11:26:492025-01-18 11:26:57

Judging History

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

  • [2025-01-18 11:26:57]
  • 评测
  • 测评结果:WA
  • 用时:39ms
  • 内存:8752kb
  • [2025-01-18 11:26:49]
  • 提交

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'