QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#424906#3223. Cellular AutomatondengziyueWA 0ms3804kbC++141.7kb2024-05-29 19:47:292024-05-29 19:47:29

Judging History

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

  • [2024-05-29 19:47:29]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3804kb
  • [2024-05-29 19:47:29]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define max_n 2200
#define inf 0x3f3f3f3f
int tid;
int n;
int m;
char s[max_n+2];
struct E{int v,w,nx;}e[max_n*2+2];
int ei=1,fir[max_n+2];
int dis[max_n+2];
bool vis[max_n+2];
int ans[max_n+2];
int anspos=-1;
void addedge(int u,int v,int w){e[++ei]=(E){v,w,fir[u]}; fir[u]=ei;}
bool spfa(){
	memset(dis,inf,sizeof(dis));
	memset(vis,0,sizeof(vis));
	queue<int>q;
	dis[0]=0; vis[0]=1; q.push(0);
	while(!q.empty()){
		int u=q.front(); q.pop(); vis[u]=false;
		for(int i=fir[u],v;i;i=e[i].nx){
			v=e[i].v;
			if(dis[u]+e[i].w<dis[v]){
				dis[v]=dis[u]+e[i].w;
				if(dis[0]<0)return false;
				if(!vis[v]){vis[v]=true; q.push(v);}
			}
		}
	}
	return dis[0]>=0;
}
bool check(){
	ei=1; memset(fir,0,sizeof(fir));
	for(int u=0,v;u<(1<<(n*2));++u){
		for(int x=0;x<=1;++x){
			v=(u*2+x)&((1<<(n*2))-1);
			if(ans[u*2+x]!=-1){addedge(u,v,ans[u*2+x]-x); addedge(v,u,x-ans[u*2+x]);}
			else{
				if(!x){addedge(u,v,1); addedge(v,u,0);}
				else{addedge(u,v,0); addedge(v,u,1);}
			}
		}
	}
	return spfa();
}
int main(){
    tid=1;
	for(int ca=1;ca<=tid;++ca){
		scanf("%d%s",&n,s); m=strlen(s);
		if(s[0]=='1'){printf("-1\n"); continue;}
		for(int i=0;i<m;++i)ans[i]=s[i]-'0';
		if(check()){printf("%s\n",s); continue;}
		anspos=-1;
		for(int i=m-1;i>=0;--i){
			if(s[i]=='1')continue;
			for(int j=0;j<i;++j)ans[j]=s[j]-'0';
			ans[i]=1;
			for(int j=i+1;j<m;++j)ans[j]=-1;
			if(check()){anspos=i; break;}
		}
		if(anspos==-1){printf("-1\n"); continue;}
		for(int i=anspos+1;i<m;++i){
			ans[i]=0;
			if(!check())ans[i]=1;
		}
		for(int i=0;i<m;++i)printf("%d",ans[i]);printf("\n");
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3804kb

input:

1
11111111

output:

-1

result:

wrong answer 1st lines differ - expected: 'no', found: '-1'