Submission #897912

#	Time	Username	Problem	Language	Result	Execution time	Memory
897912		Muhammad_Aneeq	Cave (IOI13_cave)	C++17	100 / 100	152 ms	868 KiB

cave

#include <set>
#include "cave.h"
#include <iostream>
#include <vector>
using namespace std;
int nn;
vector<int>ind;
int check(int l,int r,int S[],bool val)
{
	for (int i=l;i<=r;i++)
		S[ind[i]]=val;
	return tryCombination(S);
}
void unfill(int l,int r,int S[],bool val)
{
	for (int i=l;i<=r;i++)
			S[ind[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++)
		ind.push_back(i);
	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-i;
		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;
			}
		}
		d[ind[st]]=i;
		S[ind[st]]=z;
		// cerr<<i<<endl;
		ind.erase(begin(ind)+st);
		// cerr<<i<<endl;
	}
	ans(d,S);
}

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