Submission #749184

#	Time	Username	Problem	Language	Result	Execution time	Memory
749184		LIF	Cave (IOI13_cave)	C++14	100 / 100	519 ms	664 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 = 1;
   		int r = N - i;
		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)
   				{
		   			int cnt = 0;
		   			for(int j=0;j<N;j++)
		   			{
		   				if(state[j] == false)
						{
							cnt++;
							if(cnt == l)
							{
								s[j] ^= 1;
								break;
							}
						}
					}
					
				}
				break;
			}
   			int mid = (l+r)>>1;
   			int cnt = 0;
   			for(int j=0;j<N;j++)
   			{
   				if(state[j] == false)
				{
					cnt++;
					if(cnt >= l)
					{
						s[j] ^= 1;
						if(cnt == mid)break;
					}
					
				}
			}
			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;
		int cnt = 0;
   		for(int j=0;j<N;j++)
   		{
   			if(state[j] == false)
			{
				cnt++;		
				if(cnt == l)
				{
					state[j] = true;
					mp[j] = i;
					break;
				}
			}
		}
	/*	for(int j=0;j<N;j++)
		{
			cout<<s[j]<<" ";
		}
		cout<<endl;*/
   }
   
   answer(s,mp);
   return;
   
}

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