QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#757826#9565. Birthday Giftpiaoyun#WA 10ms8000kbC++142.0kb2024-11-17 13:50:302024-11-17 13:50:31

Judging History

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

  • [2024-11-17 13:50:31]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:8000kb
  • [2024-11-17 13:50:30]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int NR=2e5+10;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*f;
}
int n;
char s[NR];
int f[NR][2][2],g[NR][2][2];
int t[NR];
void work()
{
	scanf("%s",s+1);n=strlen(s+1);
	t[0]=1;
	for(int i=1;i<=n;i++)t[i]=0;
	memset(f[0],0x3f,sizeof(f[0]));
	memset(g[0],0,sizeof(g[0]));
	for(int i=1;i<=n;i++)
	{
		memset(f[i],0x3f,sizeof(f[i]));
		memset(g[i],0,sizeof(g[i]));
		if(s[i]!='0'){
			//1
			for(int a=0;a<=1;a++){
				for(int b=0;b<=1;b++){
					if(b==1){
						f[i][a][b^1]=min(f[i-1][a][b]-1,f[i][a][b^1]);
						g[i][a][b^1]=max(g[i-1][a][b]-1,g[i][a][b^1]);
					}
					else{
						f[i][a][b^1]=min(f[i-1][a][b]+1,f[i][a][b^1]);
						g[i][a][b^1]=max(g[i-1][a][b]+1,g[i][a][b^1]);
					}
					if(f[i][a][b^1]==0){
						f[i][a][b^1]++,t[i]=1;
						if(!g[i][a][b^1])f[i][a][b^1]=0x3f3f3f3f;
					}
				}
			}
			if(t[i-1])f[i][1][1]=1;
		}
		if(s[i]!='1'){
			//0
			for(int a=0;a<=1;a++){
				for(int b=0;b<=1;b++){
					if(b==0){
						f[i][a][b^1]=min(f[i][a][b^1],f[i-1][a][b]-1);
						g[i][a][b^1]=max(g[i][a][b^1],g[i-1][a][b]-1);
					}
					else{
						f[i][a][b^1]=min(f[i][a][b^1],f[i-1][a][b]+1);
						g[i][a][b^1]=max(g[i][a][b^1],g[i-1][a][b]+1);
					}
					if(f[i][a][b^1]==0){
						f[i][a][b^1]++,t[i]=1;
						if(!g[i][a][b^1])f[i][a][b^1]=0x3f3f3f3f;
					}
				}
			}
			if(t[i-1])f[i][0][0]=1;
		}
//		for(int a=0;a<=1;a++){
//			for(int b=0;b<=1;b++){
//				printf("dp[%d][%d][%d]=%d %d\n",i,a,b,f[i][a][b],g[i][a][b]);
//			}
//		}
//		cout<<"------------------------"<<t[i]<<endl;
	}
	int ans=0x3f3f3f3f;
	if(t[n])ans=0;
	for(int i=0;i<=1;i++)for(int j=0;j<=1;j++)ans=min(ans,f[n][i][j]);
	printf("%d\n",ans);
}
int main()
{
	int T=read();while(T--)work();
	return 0;
}
/*
5
0110101
01020102
0000021111
1012121010
0100202010
*/

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5852kb

input:

5
0110101
01020102
0000021111
1012121010
0100202010

output:

3
4
0
6
0

result:

ok 5 number(s): "3 4 0 6 0"

Test #2:

score: -100
Wrong Answer
time: 10ms
memory: 8000kb

input:

50000
1010110101
1010101010
0101010101
0101010010
0101010010
1010101010
0101001010
1010010010
0100101010
1010101001
1010100101
0101010100
0100101011
0101101010
1011010110
1011010101
1010010101
1010010010
0101010101
0010101010
0101011010
0100101010
1010101010
1010010101
1010101101
1101010101
10100101...

output:

0
10
10
4
4
10
0
4
4
6
2
8
2
2
0
4
2
4
10
8
2
4
10
2
4
8
2
8
8
4
8
4
4
6
4
4
4
6
10
10
2
0
0
10
8
10
0
10
10
10
4
10
8
10
0
8
4
0
8
2
8
0
6
2
8
10
2
10
10
2
10
2
10
8
6
4
2
8
8
0
8
10
8
10
8
10
2
6
10
4
10
8
10
4
10
6
10
10
10
6
6
6
4
10
10
10
2
2
8
10
5
10
10
8
3
10
6
10
2
2
8
2
10
4
6
0
10
2
6
2
1...

result:

wrong answer 42nd numbers differ - expected: '2', found: '0'