Submission #108968

#	Time	Username	Problem	Language	Result	Execution time	Memory
108968		Nodir_Bobiev	Cave (IOI13_cave)	C++14	12 / 100	866 ms	528 KiB

cave

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

using namespace std;
/*
int n, a[5000], b[5000];
/**/

int A[5000], B[5000], counter;
/*
void answer( int S[], int D[] )
{
	for ( int i = 0; i < n; i ++ )
		cout << S[i] << ' ';
	cout << endl;
	for ( int i = 0; i < n; i ++ )
		cout << D[i] << ' ';
	cout << endl;
	cout << "counter : " << counter << endl;
}
	
int tryCombination( int S[] )
{
	counter ++;
	for ( int i = 0; i < n; i ++ )
		cout << S[i] << ' ';
	int ans = -1;
	for ( int i = 0; i < n; i ++ ){
		if ( S[ b[i] ] != a[ b[i] ] ){
			ans = i;
			break;
		}	
	}
	cout << ": " << ans << endl;
	return ans;
}

/**/

void exploreCave( int N )
{
	int S[5000] = {};
	
	for ( int i = 0; i < N; i ++ ){
		
		for ( int j = 0; j < N; j ++ )	S[j] = A[j];
		
		int cs = tryCombination( S );
			
		int open = (cs == i ), 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 );
			
			(cs == i ? (r = m) : (l = m + 1) );
		}
		A[ ( B[i] = l ) ] = open;	
	}
	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;
}

/**/

Compilation message (stderr)

cave.cpp:7:1: warning: "/*" within comment [-Wcomment]
 /**/
  
cave.cpp:38:1: warning: "/*" within comment [-Wcomment]
 /**/
  
cave.cpp:87:1: warning: "/*" within comment [-Wcomment]
 /**/

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