Submission #587171

#	Time	Username	Problem	Language	Result	Execution time	Memory
587171		AlperenT	Cave (IOI13_cave)	C++17	100 / 100	582 ms	468 KiB

cave

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

using namespace std;

void exploreCave(int N){
	int n = N;

	vector<int> whichdoor(n, -1), curpos(n, 0);

	vector<pair<int, bool>> switches(n);

	for(int i = 0; i < n; i++) switches[i] = {i, false};

	for(int cur = 0; cur < n; cur++){
		for(int i = 0; i < cur; i++) curpos[switches[i].first] = switches[i].second;
		for(int i = cur; i < n; i++) curpos[switches[i].first] = false;

		int x = tryCombination(curpos.data());

		if(x == -1 || x > cur){
			int l = cur, r = n;

			while(r - l > 1){
				int m = l + (r - l) / 2;

				for(int i = cur; i < n; i++) curpos[switches[i].first] = true;
				for(int i = m; i < r; i++) curpos[switches[i].first] = false;

				int x = tryCombination(curpos.data());

				if(x == -1 || x > cur) l = m;
				else r = m;
			}

			swap(switches[cur], switches[l]);
			switches[cur].second = false;
			whichdoor[switches[cur].first] = cur;
		}
		else{
			int l = cur, r = n;

			while(r - l > 1){
				int m = l + (r - l) / 2;

				for(int i = cur; i < n; i++) curpos[switches[i].first] = false;
				for(int i = m; i < r; i++) curpos[switches[i].first] = true;

				int x = tryCombination(curpos.data());

				if(x == -1 || x > cur) l = m;
				else r = m;
			}

			swap(switches[cur], switches[l]);
			switches[cur].second = true;
			whichdoor[switches[cur].first] = cur;
		}
	}

	vector<int> correctpos(n);

	for(int i = 0; i < n; i++) correctpos[switches[i].first] = switches[i].second;

	answer(correctpos.data(), whichdoor.data());
}

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