Submission #945582

#	Time	Username	Problem	Language	Result	Execution time	Memory
945582		vjudge1	Cave (IOI13_cave)	C++17	100 / 100	152 ms	600 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>

using namespace std;

#define sz(s) (int)s.size()

void exploreCave(int N) {
	int s[N], ans[N], c[N];
	memset(s, 0, sizeof(s));
	int x = tryCombination(s);	
	if (x == -1) x = N;
	vector<int> p(N);
	for (int i = 0; i < N; i++) p[i] = i;
	for (int i = 0; i < N; i++) {
		x = tryCombination(s);
		bool is = 1;
		if (x == i) is = 0;
		int l = 0, r = sz(p) - 1;
		while (l <= r) {
			int m = (l + r) / 2;
			for (int j = 0; j < N; j++) c[j] = s[j];
			for (int j = l; j <= m; j++) c[p[j]] = 1;
			x = tryCombination(c);
			if (x == -1) x = N;
			if ((x == i) == is) r = m - 1;
			else l = m + 1;				                         	
		}
		r++;
		ans[p[r]] = i;
		s[p[r]] = (!is);
		p.erase(p.begin() + r);
	}
	answer(s, ans);
}

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