Submission #160110

#	Time	Username	Problem	Language	Result	Execution time	Memory
160110		Leonardo_Paes	Cave (IOI13_cave)	C++11	100 / 100	1785 ms	640 KiB

cave

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

using namespace std;

const int maxn = 5e3+10;

int n;

int door[maxn], known[maxn], state[maxn], query[maxn];

bool open(int ans, int k){
	return (ans == -1 ? 1 : ans > k);
}

void dc(int l, int r, int id, int state_id){
	if(l==r){
		door[l] = id;
		known[l] = true;
		state[l] = state_id;
		return;
	}

	int mid = (l+r) >> 1;

	memset(query, 0, sizeof query);

	for(int i=0; i<n; i++){
		if(l<=i and i<=mid) query[i] = state_id;
		else query[i] = state_id ^ 1;
	}

	for(int i=0; i<n; i++){
		if(known[i]) query[i] = state[i];
	}

	if(open(tryCombination(query), id)) dc(l, mid, id, state_id);
	else dc(mid+1, r, id, state_id);
}

void exploreCave(int N) {
	n = N;

	for(int i=0; i<n; i++){
		memset(query, 0, sizeof query);

		for(int j=0; j<n; j++){
			if(known[j]) query[j] = state[j];
		}

		if(open(tryCombination(query), i)) dc(0, n, i, 0);
		else dc(0, n, i, 1);
	}

	answer(state, door);
}

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