Submission #284035

#	Time	Username	Problem	Language	Result	Execution time	Memory
284035		Bill_00	Cave (IOI13_cave)	C++14	0 / 100	40 ms	384 KiB

cave

#include "cave.h"
int p[10000]={0},a[10000],up[10000];
void dfs(int l,int r,int L,int R,int id){
	for(int i=L;i<=R;i++){
		if(p[i]!=0) continue;
		a[i]+=1;
		a[i]%=2;
	}
	int k=tryCombination(a);
	if(L==R && k!=id){
		p[L+1]=id;
		up[L+1]=a[L+1];
		return;
	}
	if(L==R && k==id){
		p[L]=id;
		up[L]=a[L];
		return;
	}
	if(k==id){
		dfs(L,R,L,(L+R)/2,id);
	}
	else dfs(R+1,l,R+1,(R+1+l)/2,id);
}
void bfs(int l,int r,int L,int R,int id){
	for(int i=L;i<=R;i++){
		if(p[i]!=0) continue;
		a[i]+=1;
		a[i]%=2;
	}
	int k=tryCombination(a);
	if(L==R && k==id){
		p[L+1]=id;
		up[L+1]=a[L+1];
		return;
	}
	if(L==R && k!=id){
		p[L]=id;
		up[L]=a[L];
		return;
	}
	if(k!=id){
		bfs(L,R,L,(L+R)/2,id);
	}
	else bfs(R+1,l,R+1,(R+1+l)/2,id);
}
void exploreCave(int n) {
    for(int i=0;i<n;i++){
    	a[i]=1;
	}
	for(int i=1;i<=n;i++){
		int k=tryCombination(a);
		if(k!=i){
			dfs(0,n-1,0,(n-1)/2,i);
		}
		else bfs(0,n-1,0,(n-1)/2,i);
	}
	answer(up,p);
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 13
• Subtask 3: 0 / 21
• Subtask 4: 0 / 30
• Subtask 5: 0 / 24