Submission #281748

#	Time	Username	Problem	Language	Result	Execution time	Memory
281748		Saboon	Cave (IOI13_cave)	C++14	100 / 100	211 ms	760 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 10;

int s[maxn], p[maxn];

void exploreCave(int n){
	vector<int> Key;
	for (int i = 0; i < n; i++)
		Key.push_back(i);
	for (int i = 0; i < n; i++){
		int lo = 0, hi = Key.size();
		bool last = (tryCombination(s) == i);
		while (hi - lo > 1){
			int mid = (lo + hi) >> 1;
			for (int j = lo; j < mid; j++)
				s[Key[j]] ^= 1;
			bool now = (tryCombination(s) == i);
			if (now == last)
				lo = mid;
			else
				hi = mid, last ^= 1;
		}
		if (last == 1)
			s[Key[lo]] ^= 1;
		p[Key[lo]] = i;
		Key.erase(Key.begin()+lo);
	}
	answer(s, p);
}

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