Submission #1163352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163352		boclobanchat	Cave (IOI13_cave)	C++20	100 / 100	144 ms	516 KiB

cave

#include"cave.h"
#include<bits/stdc++.h>
using namespace std;
int tryCombination(int S[]);
void exploreCave(int N)
{
	int pos[N],A[N],ans[N];
	bool ck[N];
	for(int i=0;i<N;i++) ck[i]=true,pos[i]=0;
	int pf=tryCombination(pos);
	if(pf==-1) pf=N+1;
	for(int i=0;i<N;i++)
	{
		int l=0,r=N-1,p=-1,pp,g,f;
		while(p<N-1) p++,pos[p]^=ck[p];
		f=tryCombination(pos);
		if(f==-1) f=N+1;
		bool e=(pf<f);
		while(l<=r)
		{
			int mid=(l+r)/2;
			while(p<mid) p++,pos[p]^=ck[p];
			while(p>mid) pos[p]^=ck[p],p--;
			int res=tryCombination(pos);
			if(res==-1) res=N+1;
			if(e)
			{
				if(res!=pf) r=mid-1,pp=mid,g=res;
				else l=mid+1;
			}
			else
			{
				if(res==f) r=mid-1,pp=mid,g=pf;
				else l=mid+1;
			}
		}
		while(p<pp) p++,pos[p]^=ck[p];
		while(p>pp) pos[p]^=ck[p],p--;
		if(e);
		else while(p>=0) pos[p]^=ck[p],p--;
		A[pp]=i,pf=g,ck[pp]=false;
	}
	answer(pos,A);
}

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