Submission #290665

#	Time	Username	Problem	Language	Result	Execution time	Memory
290665		Bill_00	Cave (IOI13_cave)	C++14	100 / 100	277 ms	652 KiB

cave

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

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