Submission #228263

#	Time	Username	Problem	Language	Result	Execution time	Memory
228263		bharat2002	Cave (IOI13_cave)	C++14	100 / 100	349 ms	632 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
const int N=5e3 +10;
const int mod=1e9 + 7;
#define pii pair<int, int>
#define f first
#define s second 
#define mp make_pair
#define FOR(i, n) for(int i=1;i<=n;i++)
#define TRACE(x) cerr << #x << " = " << x << endl 
//Trace prints the name of the variable and the value.
int n;int cur[N], match[N], ans[N];//match is D answer function ka. cur will be S.
bool change[N];
void exploreCave(int NC)
{
	n=NC;
	for(int i=0;i<n;i++) 
	{
		change[i]=1;cur[i]=0;
	}
	for(int i=0;i<n;i++)
	{
		int ret=tryCombination(cur);int corr;
		if(ret==i) corr=1;
		else corr=0;
		int low=0, high=n-1;
		while(high-low>1)
		{
			int mid=(low+high)/2;
			for(int j=low;j<=mid;j++)
				cur[j]^=change[j];
			ret=tryCombination(cur);
			if(corr==0)
			{
				if(ret>i||ret==-1) low=mid+1;
				else high=mid;
			}
			else
			{
				if(ret>i||ret==-1) high=mid;
				else low=mid+1;
			}
			for(int j=low;j<=mid;j++)
				if(change[j]) cur[j]=0;
		}
		if(corr==1)
		{
			cur[high]^=change[high];ret=tryCombination(cur);
			if(ret>i||ret==-1) {low=high;}
		}
		else
		{
			cur[high]^=change[high];ret=tryCombination(cur);
			if(ret==i) {low=high;}	
		}
		change[low]=0;cur[low]=corr;match[low]=i;
		for(int j=0;j<n;j++)
			if(change[j]) cur[j]=0;
	}
	answer(cur, match);
}

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