Submission #896691

#	Time	Username	Problem	Language	Result	Execution time	Memory
896691		aqxa	Cave (IOI13_cave)	C++17	0 / 100	1 ms	860 KiB

cave

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

const int mxn = 5001; 

using ll = long long; 

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); 
			if (can2 == -1) can2 = n; 
			can2 = (can > i); 
			if (can == can2) {
				lo = mid + 1; 
			} else {
				hi = mid; 
				can = can2; 
			}
		}
		assert(need[lo] == -1); 
		need[lo] = can ^ t[lo] ^ 1; 
		ans[lo] = i; 
	}
	answer(need, ans); 
}

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