Submission #988355

#	Time	Username	Problem	Language	Result	Execution time	Memory
988355		Muaath_5	Cave (IOI13_cave)	C++17	100 / 100	303 ms	860 KiB

cave

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

const int N = 2e5+1;

#ifndef MUAATH_5
#include "cave.h"
#endif

int tryCombination(int c[]);

void answer(int s[], int d[]);

void exploreCave(int n) {
	int sure[n] = {};
	int correct[n] = {};
	int index[n] = {};
	for (int i = 0; i < n; i++) {
		int open = (tryCombination(correct) == i ? 1 : 0);
		int l = 0, r = n-1;
		while (l < r) {
			const int mid = (l+r)/2;
			int cpy[n];
			for (int i = 0; i < n; i++)
				cpy[i] = correct[i];
			if (!open) {
				for (int i = mid+1; i < n; i++)
					if (!sure[i])				
						cpy[i] = 1;
			}
			else {
				for (int i = 0; i <= mid; i++)
					if (!sure[i])
						cpy[i] = 1;
			}
			if (tryCombination(cpy) == i)
				l = mid+1;
			else
				r = mid;
		} 
		index[i] = l;
		correct[l] = open;
		sure[l] = 1;
	}
	int idx[n] = {};
	for (int i = 0; i < n; i++)
		idx[index[i]] = i;
	answer(correct, idx);
}

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