Submission #167630

#	Time	Username	Problem	Language	Result	Execution time	Memory
167630		Eae02	Cave (IOI13_cave)	C++17	100 / 100	953 ms	640 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
using namespace std;

void exploreCave(int N) {
	vector<pair<int, bool>> known;
	
	for (int cur = 0; cur < N; cur++) {
		vector<int> query1(N, 0);
		for (auto& k : known)
			query1[k.first] = k.second;
		
		bool correctState = tryCombination(query1.data()) == cur;
		
		int lo = 0;
		int hi = N;
		while (hi > lo + 1) {
			int mid = (lo + hi) / 2;
			vector<int> query(N, correctState);
			for (int i = lo; i < mid; i++)
				query[i] = !correctState;
			for (auto& k : known)
				query[k.first] = k.second;
			
			if (tryCombination(query.data()) == cur) {
				hi = mid;
			} else {
				lo = mid;
			}
		}
		known.emplace_back(lo, correctState);
	}
	
	vector<int> S(N);
	vector<int> D(N);
	for (int i = 0; i < N; i++) {
		S[known[i].first] = known[i].second;
		D[known[i].first] = i;
	}
	
	answer(S.data(), D.data());
}

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