Submission #106359

#	Time	Username	Problem	Language	Result	Execution time	Memory
106359		DystoriaX	Cave (IOI13_cave)	C++14	100 / 100	560 ms	588 KiB

cave

#include "cave.h"

#include <bits/stdc++.h>

using namespace std;

int n;
int s[5010], d[5010], tmp;
bool al[5010];

void findElement(int idx){
	int ret = 0;

	for(int i = 0; i < n; i++){
		if(!al[i]) s[i] = 1;
	}

	ret = tryCombination(s);

	if(ret == idx) tmp = 1;
	else tmp = 0;
	//Real answer should be 1 - tmp

	int l, r, mid;

	l = 0, r = n - 1;
	while(l < r){
		mid = (l + r) >> 1;

		for(int i = l; i <= mid; i++) if(!al[i]) s[i] = tmp;
		for(int i = mid + 1; i <= r; i++) if(!al[i]) s[i] = 1 - tmp;

		ret = tryCombination(s);

		if(ret == idx) r = mid;
		else l = mid + 1;
	}

	d[l] = idx;
	s[l] = 1 - tmp;
	al[l] = 1;
}

void exploreCave(int N) {
	n = N;

	for(int i = 0; i < n; i++){
		findElement(i);
	}

	answer(s, d);
}

//g++ -Wall -lm -static -DEVAL -o cave -O2 -DEVAL grader.c cave.cpp -std=c++14

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