Submission #420269

#	Time	Username	Problem	Language	Result	Execution time	Memory
420269		SuhaibSawalha1	Cave (IOI13_cave)	C++17	100 / 100	1112 ms	472 KiB

cave

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

void exploreCave(int N) {
	int a[N] = {}, D[N], P[N] = {};
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (!P[j]) {
				a[j] = 0;
			}
		}
		int right = tryCombination(a) != i;
		int l = 0, r = N - 1; 
		while (l < r) {
			int mid = (l + r) / 2;
			for (int j = 0; j < N; ++j) {
				if (!P[j]) {
					a[j] = j <= mid ? right : !right;
				}
			}
			if (tryCombination(a) == i) {
				r = mid;
			}
			else {
				l = mid + 1;
			}
		}
		D[l] = i;
		a[l] = !right;
		P[l] = 1;
	}
	answer(a, D);
}

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