Submission #109236

#	Time	Username	Problem	Language	Result	Execution time	Memory
109236		Nodir_Bobiev	Cave (IOI13_cave)	C++14	100 / 100	685 ms	640 KiB

cave

# include "cave.h"
# include <iostream>
# include <vector>

using namespace std;
 
void exploreCave( int N )
{
	int A[5001] = {}, B[5001] = {};
	vector < int > vc;
	
	for ( int i = 0; i < N; i ++ )	vc.push_back(i);
		
	for ( int i = 0; i < N; i ++ ){
			
		for ( auto c: vc )	A[c] = 0;
		
		int cs = tryCombination( A );
		
		int open = (cs == i ), l = 0, r = vc.size() - 1;
		
		while( r > l  ){
			
			int m = ( l + r ) >> 1;
			
			for ( auto c: vc ) A[ c ] = open;
			
			for ( int j = l; j <= m; j ++ )	A[ vc[j] ] = 1 - open;
				
			int cs = tryCombination( A );
			
			(cs == i ? (r = m) : (l = m + 1) );
		}
		B[vc[l]] = i;
		A[ vc[l] ] = open;	
		vc.erase( vc.begin() + l );
	}
	
	answer( A, B );
}

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