Submission #108959

#	Time	Username	Problem	Language	Result	Execution time	Memory
108959		Nodir_Bobiev	Cave (IOI13_cave)	C++14	0 / 100	7 ms	384 KiB

cave

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

using namespace std;

int n, a[5000], b[5000];
int A[5000], B[5000], counter;
/*
bool answer( int S[], int D[] )
{
	bool T = true;
	for ( int i = 0; i < n; i ++ ){
		if( S[i] != a[i] )
			T = false;
	}
	for ( int i = 0; i < n; i ++ ){
		if( D[i] != b[i] )
			T = false;
	}
	
	cout << ( T? "YES":"NO" ) << endl;
	cout << "counter :" << counter << endl;
	
	return T;
}
	
int tryCombination( int S[] )
{
	counter ++;
	for ( int i = 0; i < n; i ++ ){
		if ( S[ b[i] ] != a[ b[i] ] )
			return i;
	}
	return -1;
}
*/

void exploreCave( int N )
{
	int S[5000] = {};
	
	fill( B, B + n, 5000 );
	
	for ( int i = 0; i < n; i ++ ){
		
		for ( int j = 0; j < n; j ++ )
			S[j] = 0;
		for ( int j = 0; j < i; j ++ )
			S[ B[j] ] = A[ B[j] ];
		
		int cs = tryCombination( S );
		
		/*
		for ( int j = 0; j < n; j ++ )
			cout << S[j] << ' ';
		
		cout << cs << endl;
		*/
		
		int open = 0;
		if( cs == i )
			open = 1;
		
			
		int l = 0, r = n - 1;
		while( r > l  ){
			int m = ( l + r ) >> 1;
			
			for ( int j = 0; j < n; j ++ )
				S[j] = open;
			for ( int j = l; j <= m; j ++ )
				S[j] = 1 - open;
			for ( int j = 0; j < i; j ++ )
				S[ B[j] ] = A[ B[j] ];
				
			int cs = tryCombination( S );
			
			if( cs == i )
				r = m;
			else
				l = m + 1;
		}
		B[i] = l;
		A[ B[i] ] = open;
		
		//cout << i << ' ' << B[i] << ' ' << A[ B[i] ] << endl;
	}
	answer( A, B );
}

/*
int main()
{
	cin >> n;
	
	for ( int i = 0; i < n; i ++ )
		cin >> a[i];
		
	for ( int i = 0; i < n; i ++ )
		cin >> b[i];
	
	exploreCave( n );
	
	return 0;
}
*/

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