Submission #258409

#	Time	Username	Problem	Language	Result	Execution time	Memory
258409		SpeedOfMagic	Cave (IOI13_cave)	C++17	0 / 100	175 ms	640 KiB

cave

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

void exploreCave(int N) {
    vector<int> switches;
	for (int i = 0; i < N; ++i)
		switches.push_back(i);
	
	int correct[N]; int perm[N];
	for (int i = 0; i < N; ++i)
		correct[i] = 0;
	int current = tryCombination(correct);
	
	for (int i = 1; i <= N; ++i) {
		if (current == i) {
			for (int j : switches)
				correct[j] = 1;
			current = tryCombination(correct);
			assert(current > i);
		}
		int l = 0, r = switches.size() - 1;
		while (l < r) {
			int mid = (l + r) >> 1;
			for (int i = l; i <= mid; ++i)
				correct[switches[i]] = 1 - correct[switches[i]];
			int pos = tryCombination(correct);
			for (int i = l; i <= mid; ++i)
				correct[switches[i]] = 1 - correct[switches[i]];
			if (pos == i) {
				r = mid;
			} else {
				l = mid + 1;
			}
		}
		
		perm[switches[l]] = i - 1;
		switches.erase(switches.begin() + l);
	}
	
	answer(correct, perm);
}

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