记录编号 38780 评测结果 AAAAA
题目名称 [IOI 1998] 灯光 最终得分 100
用户昵称 GravatarQhelDIV 是否通过 通过
代码语言 C++ 运行时间 0.090 s
提交时间 2012-06-12 21:26:32 内存使用 0.00 MiB
显示代码纯文本
#include <fstream>
#include <set>
using namespace std;
ifstream fin("partya.in");
ofstream fout("partya.out");
int N,C,F[200],A[200];
bool flag[200];
set<string>Set;
void Initialize()
{
	fin>>N>>C;
	for(int i=1;i<=N;i++)
		A[i]=1;
int g;
	fin>>g;
	while(g!=-1)
	{
		flag[g]=true;
		F[g]=1;
		fin>>g;
	}
	fin>>g;
	while(g!=-1)
	{
		flag[g]=true;
		fin>>g;
	}
}

void Change(int pos)
{
int i;
	if(pos==1)
	{
		for(i=1;i<=N;i++)
			A[i]=1-A[i];
	}
	if(pos==2)
	{
		for(i=1;i<=N;i++)
			if(i%2!=0)
				A[i]=1-A[i];
	}
	if(pos==3)
	{
		for(i=1;i<=N;i++)
			if(i%2==0)
				A[i]=1-A[i];
	}
	if(pos==4)
	{
		for(i=1;i<=N;i++)
			if(i%3==1)
				A[i]=1-A[i];
	}
}

void DFS(int pos,int num)
{
int i;
	if(num>C)
		return;
	if((pos==4) && (C-num)%2==0)
	{
		string S="\0";
		for(i=1;i<=N;i++)
			if(flag[i] && F[i]!=A[i])
				return;
		for(i=1;i<=N;i++)
			S+='0'+A[i];
		Set.insert(S);
		return;
	}
	if(pos==4)
		return;
	pos++;
	DFS(pos,num);
	Change(pos);
	DFS(pos,num+1);
	Change(pos);
}

void Op()
{
set<string>::iterator it,en=Set.end();
	for(it=Set.begin();it!=en;it++)
		fout<<*it<<endl;
	
}

int main()
{
	Initialize();
	
	DFS(0,0);
	
	Op();
	
	fin.close();
	fout.close();
	return 0;
}