Submission #897911

#	Time	Username	Problem	Language	Result	Execution time	Memory
897911		Muhammad_Aneeq	Cave (IOI13_cave)	C++17	13 / 100	57 ms	584 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]={};
	int x=-2;
	for (int i=0;i<n;i++)
		ind.push_back(i);
	for (int i=0;i<n;i++)
	{
		if (x==-2)
			x=tryCombination(S);
		if (x==-1)
			ans(d,S);
		bool z=(x==i);
		int st=0,en=ind.size()-1;

		while (st!=en)
		{
			int mid=(st+en)/2;
			x=check(st,mid,S,1);
			if (x==-1)
				ans(d,S);
			unfill(st,mid,S,0);
			if (z==0)
			{
				if (x==i)
					en=mid;
				else
					st=mid+1;
			}
			else
			{
				if (x>i)
					en=mid;
				else
					st=mid+1;
			}
		}
		d[ind[st]]=i;
		S[ind[st]]=z;
		ind.erase(begin(ind)+st);
	}
	ans(d,S);
}

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