QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#646376#3223. Cellular AutomatonsyxsyxWA 0ms3836kbC++141.4kb2024-10-16 22:34:392024-10-16 22:34:39

Judging History

This is the latest submission verdict.

  • [2024-10-16 22:34:39]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3836kb
  • [2024-10-16 22:34:39]
  • Submitted

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'