Submission #897910

#	Time	Username	Problem	Language	Result	Execution time	Memory
897910		Muhammad_Aneeq	Cave (IOI13_cave)	C++17	64 / 100	125 ms	600 KiB

cave

#include <set>
#include "cave.h"
#include <iostream>
using namespace std;
int const MAXN=5e3+10;
bool vis[MAXN]={};
int nn;
int check(int l,int r,int S[],bool val)
{
	for (int i=l;i<=r;i++)
	{
		if (vis[i])
			continue;
		S[i]=val;
	}
	return tryCombination(S);
}
void unfill(int l,int r,int S[],bool val)
{
	for (int i=l;i<=r;i++)
		if (!vis[i])
			S[i]=val;
}
void ans(int d[],int S[])
{
	for (int i=0;i<nn;i++)
	{
		S[i]^=1;
		int z=tryCombination(S);
		d[i]=z;
		S[i]^=1;
	}
	answer(S,d);
	exit(0);
}
void exploreCave(int n)
{
	nn=n;
	int d[n]={},S[n]={};
	for (int i=0;i<n;i++)
	{
		int x=tryCombination(S);
		if (x==-1)
			ans(d,S);
		bool z=(x==i);
		int st=0,en=n-1;
		while (st!=en)
		{
			int mid=(st+en)/2;
			int f=check(st,mid,S,1);
			if (f==-1)
				ans(d,S);
			unfill(st,mid,S,0);
			if (z==0)
			{
				if (f==i)
					en=mid;
				else
					st=mid+1;
			}
			else
			{
				if (f>i)
					en=mid;
				else
					st=mid+1;
			}
		}
		// cout<<st<<' '<<i<<endl;
		d[st]=i;
		S[st]=z;
		vis[st]=1;
	}
	ans(d,S);
}

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