Submission #248946

#	Time	Username	Problem	Language	Result	Execution time	Memory
248946		Dilshod_Imomov	Cave (IOI13_cave)	C++17	0 / 100	667 ms	632 KiB

cave

# include "cave.h"
# include <bits/stdc++.h>
using namespace std;

const int MAX_N = 5007;

pair < int, int > sw[MAX_N], door[MAX_N];
int n, counts;

void input() {
	cin >> n;
	for ( int i = 0; i < n; i++ ) {
		int x, y;
		cin >> x >> y; // switch i connects door x when on y
		sw[i] = {x, y};
		door[x] = { i, y };
	}
}

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);
}

vector < int > create( vector < int > vc ) {
	for ( int i = 0; i < (int)vc.size(); i++ ) {
		if ( vc[i] == -1 ) {
			vc[i] = 1;
		}
	}
	return vc;
} 

int can( vector < 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( vector < 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) {
	n = N;
	vector < int > doors(N, -1), S(N), D(N);
	int cnt = N - 1; 
	for ( int i = 0; i < N; i++ ) {
		int fdoor = tryCombination( create(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( 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(doors, l);
		doors[x] = ans;
		S[x] = ans;
		D[x] = i;
		cnt--;
	}
	answer(S, D);
}
/*
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