Submission #896695

#	Time	Username	Problem	Language	Result	Execution time	Memory
896695		aqxa	Cave (IOI13_cave)	C++17	100 / 100	167 ms	760 KiB

cave

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

#include "cave.h"

const int mxn = 5001; 
using ll = long long; 

// namespace tester {
// 	int N; 
// 	int to[mxn], need[mxn]; 
// 	void init() {
// 		cin >> N; 
// 		for (int i = 0; i < N; ++i) {
// 			cin >> need[i]; 
// 		}
// 		for (int i = 0; i < N; ++i) {
// 			cin >> to[i]; 
// 		}
// 	}
// 	int tryCombination(int comb[]) {
// 		int mn = N; 
// 		for (int i = 0; i < N; ++i) {
// 			if (comb[i] != need[i]) {
// 				mn = min(mn, to[i]); 
// 			}
// 		}
// 		if (mn == N) mn = -1; 
// 		return mn; 
// 	}
// 	void answer(int need2[], int to2[]) {
// 		bool ok = 1; 
// 		for (int i = 0; i < N; ++i) {
// 			ok &= to[i] == to2[i] && need[i] == need2[i]; 
// 		}
// 		if (ok) {
// 			cout << "AC\n";
// 		} else {
// 			cout << "WA\n";
// 			cout << "Participant response: \n";
// 			for (int i = 0; i < N; ++i) {
// 				cout << need2[i] << " \n"[i == N - 1]; 
// 			}
// 			for (int i = 0; i < N; ++i) {
// 				cout << to2[i] << " \n"[i == N - 1]; 
// 			}
// 		}
// 	}
// }
// using namespace tester; 


void exploreCave(int n) {
	int ans[n], need[n]; 
	for (int i = 0; i < n; ++i) {
		need[i] = -1; 
	}

	int t[n]; 
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			t[j] = (need[j] == -1 ? 0 : need[j]); 
		}
		int can = tryCombination(t); 
		if (can == -1) can = n; 
		can = (can > i); 

		int lo = 0, hi = n - 1; 
		while (lo < hi) {
			int mid = (lo + hi) / 2; 
			for (int j = lo; j <= mid; ++j) {
				t[j] = (need[j] == -1 ? t[j] ^ 1 : need[j]); 
			}
			int can2 = tryCombination(t); 
			// for (int j = 0; j < n; ++j) {
			// 	cout << t[j] << " \n"[j + 1 == n]; 
			// }
			// cout << "res " << can2 << '\n';

			if (can2 == -1) can2 = n; 
			can2 = (can2 > i); 
			if (can == can2) {
				lo = mid + 1; 
			} else {
				hi = mid; 
				can = can2; 
			}
		}
		need[lo] = can ^ t[lo] ^ 1; 
		ans[lo] = i; 
	}
	answer(need, ans); 
}

// int main() {
// 	ios::sync_with_stdio(false);
// 	cin.tie(nullptr);
	
// 	init(); 
// 	exploreCave(N); 

// 	return 0; 
// }

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