Submission #160112

#	Time	Username	Problem	Language	Result	Execution time	Memory
160112		Leonardo_Paes	Cave (IOI13_cave)	C++11	100 / 100	1427 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, state_id^1, sizeof query);
 
	for(int i=l; i<=mid; i++){
		query[i] = state_id;
	}
 
	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