Submission #248962

#	Time	Username	Problem	Language	Result	Execution time	Memory
248962		Dilshod_Imomov	Cave (IOI13_cave)	C++17	0 / 100	147 ms	384 KiB

cave

# include "cave.h"
# include <bits/stdc++.h>
using namespace std;
/*
int tryCombination(vector < int > S ) {
	counts++;
	for ( int i = 0; i < n; i++ ) {
		if ( S[door[i].first] == door[i].second ) {
			continue;
		}
		return i;
	}
	return -1;
}

void answer( vector < int > S, vector < int > D ) {
	for ( int i = 0; i < n; i++ ) {
		int dr = D[i], t = S[i];
		cout << S[i] << ' ' << D[i] << '\n';
		if ( door[dr].first != i || door[dr].second != t ) {
			// cout << "Wrong Answer" << '\n';
			// exit(0);
		}
	}
	cout << "Accepted with " << counts << " counts.\n";
	exit(0);
}
*/
auto create( int n, int vc[] ) {
	for ( int i = 0; i < n; i++ ) {
		if ( vc[i] == -1 ) {
			vc[i] = 1;
		}
	}
	return vc;
} 

int can( int n, int doors[], int mid, int l, int r  ) {
	int cnt = mid, cntl = 0;
	for ( int i = 0; i < n; i++ ) {
		if ( doors[i] != -1 ) {
			continue;
		}
		if ( cntl < l ) {
			doors[i] = 1;
			cntl++;
			continue;
		}
		if ( cnt ) {
			doors[i] = 0;
			cnt--;
		}
		else {
			doors[i] = 1;
		}
	}
	return tryCombination(doors);
}

int find( int n, int doors[], int l ) {
	int cnt = 0;
	for ( int i = 0; i < n; i++ ) {
		if ( doors[i] != -1 ) {
			continue;
		}
		if ( cnt == l ) {
			return i;
		}
		cnt++;
	}
	return 0;
}

void exploreCave(int N) {
	int n = N;
	int doors[N], S[N], D[N];
	for ( int i = 0; i < n; i++ ) {
		doors[i] = -1;
	}
	int cnt = N - 1; 
	for ( int i = 0; i < n; i++ ) {
		int fdoor = tryCombination( create(n, doors) );
		int ans = 0;
		if ( fdoor != i ) {
			ans = 1;
		}
		int l = 0, r = cnt, mid;
		while ( l < r ) {
			mid = (l + r) / 2;
			int x = can( n, doors, mid - l + 1, l, r );
			if ( x != i ) {
				if ( ans == 0 ) {
					r = mid;
				}
				else {
					l = mid + 1;
				}
			}
			else {
				if ( ans == 0 ) {
					l = mid + 1;
				}
				else {
					r = mid;
				}
			}
		}
		int x = find(n, doors, l);
		doors[x] = ans;
		S[x] = ans;
		D[x] = i;
		cnt--;
	}
	answer(S, D);
	exit(0);
}
/*
int main()
{
	input();
	exploreCave(n);
	return 0;
}
*/

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