Submission #109230

#	Time	Username	Problem	Language	Result	Execution time	Memory
109230		Nodir_Bobiev	Cave (IOI13_cave)	C++14	12 / 100	880 ms	512 KiB

cave

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

using namespace std;
/*
int n, s[5001], d[5001], counter;

int tryCombination( int S[] )
{
	counter ++;
	for ( int i = 0; i < n; i ++ ){
		if ( S[d[i]] != s[d[i]] ){
			return i;
		}
	}
	return -1;
}

void answer( int S[], int D[] )
{
	bool T = true;
	for ( int i = 0; i < n; i ++ )
		if( S[i] != s[i] || D[i] != d[i] )
			T = false;
	
	if( T ){
		cout << endl;
		cout << "WRONG ANSWER!";
		cout << endl;
	}
	else{
		cout << endl;
		cout << "ACCEPTED!";
		cout << endl;
	}
	cout << "counter : " << counter << endl;
	
	return;
}
*/
void exploreCave( int N )
{
	bool used[N] = {};
	int S[N] = {}, D[N] = {};
	
	for ( int i = 0; i < N; i ++ ){

		for ( int j = 0; j < N; j ++ )
			if( used[j] == false )
				S[j] = 0;

		int num = tryCombination( S );
		int open = ( num == i );
		
		int l = 0, r = N - 1;
		
		while( l < r ){
			int m = ( l + r ) >> 1;
			
			for ( int j = 0; j < N; j ++ ){
				if( used[j] == false ){
					if( j < l || m < j )
						S[j] = open;
					else
						S[j] = 1 - open;
				}
			}
			num = tryCombination( S );
			if( num == i )
				r = m;
			else
				l = m + 1;
		}
		used[l] = true;
		S[l] = open;
		D[i] = l;
	}
	answer( S, D );
}
/*
int main()
{
	cin >> n;
	
	for ( int i = 0; i < n; i ++ ){
		cin >> s[i];
	}
	for ( int i = 0; i < n; i ++ ){
		cin >> d[i];
	}
	
	exploreCave( n );
	
	cout << endl;
	cout << "THE END!" << endl;
	return 0;
}
*/

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