Submission #249018

#	Time	Username	Problem	Language	Result	Execution time	Memory
249018		Dilshod_Imomov	Cave (IOI13_cave)	C++17	100 / 100	1126 ms	760 KiB

cave

# include <bits/stdc++.h>
# include "cave.h"
using namespace std;
/*
int S[5007], D[5007], n, counts;
set < pair < int, pair < int, int > > > st;

int tryCombination( int doors[] ) {
	counts++;
	for ( auto pr: st ) {
		int ind = pr.second.first, correct = pr.second.second;
		if ( doors[ind] != correct ) {
			return pr.first;
		}
	}
	return -1;
}

void answer( int s[], int d[] ) {
	int ok = 1;
	for ( int i = 0; i < n; i++ ) {
		if ( s[i] != S[i] || d[i] != D[i] ) {
			ok = 0;
		}
		cout << s[i] << ' ';
	}
	cout << '\n';
	for ( int i = 0; i < n; i++ ) {
		cout << d[i] << ' ';
	}
	cout << '\n';
	if ( ok ) {
		cout << "Accepted with " << counts << " counts.";
	}
	else {
		cout << "Wrong Answer!";
	}
}
*/
void exploreCave( int n ) {
	int doors[n + 10], _doors[n], cnt_unknown = n, s[n], d[n];
	for ( int i = 0; i < n; i++ ) {
		doors[i] = -1;
	}
	for ( int i = 0; i < n; i++ ) {
		for ( int j = 0; j < n; j++ ) {
			if ( doors[j] != -1 ) {
				_doors[j] = doors[j];
			}
			else {
				_doors[j] = 1;
			}
		}
		int ans = 0, x = tryCombination( _doors );
		if ( x != i ) {
			ans = 1;
		}
		// cout << "Done 2 " << i << " " << ans << endl;
		int l = 0, r = cnt_unknown - 1, mid;
		while ( l < r ) {
			mid = (l + r) / 2;
			int c = 0;
			for ( int j = 0; j < n; j++ ) {
				if ( doors[j] != -1 ) {
					_doors[j] = doors[j];
				}
				else {
					if ( c >= l && c <= mid ) {
						_doors[j] = 0;
					}
					else {
						_doors[j] = 1;
					}
					c++;
				}
			}
			if ( tryCombination( _doors ) != i ) {
				if ( !ans ) {
					r = mid;
				}
				else {
					l = mid + 1;
				}
			}
			else {
				if ( !ans ) {
					l = mid + 1;
				}
				else {
					r = mid;
				}
			}
		}
		// cout << "Done 3 " << i << ' ' << l << endl;
		int ind, c = 0;
		for ( int j = 0; j < n; j++ ) {
			if ( doors[j] != -1 ) {
				continue;
			}
			if ( c == l ) {
				ind = j;
				break;
			}
			c++;
		}
		// cout << ind << endl;
		s[ind] = doors[ind] = ans;
		d[ind] = i;
	}
	answer( s, d );
	exit(0);
}
/*
int main() {
	cin >> n;
	for ( int i = 0; i < n; i++ ) {
		cin >> S[i];
	}
	for ( int i = 0; i < n; i++ ) {
		cin >> D[i];
		st.insert( { D[i], { i, S[i] } } );
	}
	exploreCave(n);
}
*/

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:107:23: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   s[ind] = doors[ind] = ans;
            ~~~~~~~~~~~^~~~~

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