QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#646376 | #3223. Cellular Automaton | syxsyx | WA | 0ms | 3836kb | C++14 | 1.4kb | 2024-10-16 22:34:39 | 2024-10-16 22:34:39 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=205,M=2005;
int w,n,S;
int s[N];
int dis[N];
int m;
struct E{int u,v,w;}e[M];
//x->y
bool check(int lim)
{
m=0;
for(int i=0;i<(n>>1);i++)
{
int now=i<<1;
int x=i,y=now&S,t=0;
int liml=0,limr=1;
if(now<=lim) liml=limr=s[now];
e[++m]=(E){x,y,limr-t};
e[++m]=(E){y,x,t-liml};
now=i<<1|1;
x=i,y=now&S,t=1;
liml=0,limr=1;
if(now<=lim) liml=limr=s[now];
e[++m]=(E){x,y,limr-t};
e[++m]=(E){y,x,t-liml};
}
memset(dis,0x3f,sizeof(dis));
dis[0]=0;
for(int i=1;i<=20;i++)
for(int j=1;j<=m;j++)
dis[e[j].v]=min(dis[e[j].v],dis[e[j].u]+e[j].w);
return dis[0]==0;
}
bool dfs(int x,int op)
{
printf("%d %d\n",x,op);
if(!check(x-1)) return false;
if(x==n) return true;
int tmp=s[x];
if(op==0)
{
if(s[x]==0)
{
s[x]=0;
if(dfs(x+1,0)) return true;
s[x]=1;
if(dfs(x+1,1)) return true;
s[x]=tmp;
return false;
}
else
{
if(dfs(x+1,0)) return true;
s[x]=tmp;
return false;
}
}
if(op==1)
{
s[x]=0;
if(dfs(x+1,1)) return true;
s[x]=1;
if(dfs(x+1,1)) return true;
s[x]=tmp;
return false;
}
}
int main()
{
scanf("%d",&w);
n=1<<(2*w+1);
S=(1<<(2*w))-1;
for(int i=0;i<n;i++) scanf("%1d",&s[i]);
if(!dfs(0,0)) printf("no");
else for(int i=0;i<n;i++) printf("%d",s[i]);
printf("\n");
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3836kb
input:
1 11111111
output:
0 0 1 0 no
result:
wrong answer 1st lines differ - expected: 'no', found: '0 0'