Submission #749100

#	Time	Username	Problem	Language	Result	Execution time	Memory
749100		LIF	Cave (IOI13_cave)	C++14	51 / 100	128 ms	404 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
int s[5005];
int state[5005];
int now[5005];
int last[5005];
int mp[5005];
void exploreCave(int N) {
   
   for(int i=0;i<N;i++)
   {
   		int l = 0;
   		int r = N-1;
		int xx = tryCombination(s);
   		if(xx != i) now[i] = true;
   		else now[i] = false;
   	//	cout<<"pre"<<" "<<now[i]<<endl;
   	//	cout<<"i"<<i<<endl;
   		while(l<=r)
   		{
   //			cout<<"l r"<<l<<" "<<r<<endl;
   			if(l == r)
   			{
   				int xx = tryCombination(s);
   				if(xx == i)
   				{
   					s[l] ^=1;
				}
				break;
			}
   			int mid = (l+r)>>1;
   			for(int j=l;j<=mid;j++)
   			{
   				if(state[j] == false)s[j] ^= 1;
			}
			int xx = tryCombination(s);
		//	cout<<"xx"<<xx<<endl;
			bool flag = false;
			if(xx != i)flag = true;
		//	cout<<"flag"<<flag<<endl;
			if(now[i] == flag)
			{
		//		cout<<"yeah"<<endl;
				l = mid+1;
			}
			else
			{
				r = mid;
			}
			
			now[i] = flag;
		}
	//	cout<<l<<endl;
		
		state[l] = true;
		mp[l] = i;
	/*	for(int j=0;j<N;j++)
		{
			cout<<s[j]<<" ";
		}
		cout<<endl;*/
   }
   
   answer(s,mp);
   return;
   
}

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