QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#424906 | #3223. Cellular Automaton | dengziyue | WA | 0ms | 3804kb | C++14 | 1.7kb | 2024-05-29 19:47:29 | 2024-05-29 19:47:29 |
Judging History
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'