Submission #233797

#	Time	Username	Problem	Language	Result	Execution time	Memory
233797		cfalas	Cave (IOI13_cave)	C++14	51 / 100	539 ms	876 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
#define MID ((l+r)/2)

int n;
bool used[10000000] = {};
int state[10000000] = {};
int cnt=0;
int query(int l, int r, int sttate){
	if(l>=r) return l;
	int a[n] = {};
	for(int i=0;i<l;i++){
		if(used[i]) a[i] = state[i];
		else a[i] = 1-sttate;
	}
	for(int i=l;i<=MID;i++){
		if(used[i]) a[i] = state[i];
		else a[i] = sttate;
	}
	for(int i=MID+1;i<n;i++){
		if(used[i]) a[i] = state[i];
		else a[i] = 1-sttate;
	}
	//for(int i=0;i<n;i++) cout<<a[i]<<" ";
	//cout<<endl;
	//cout<<tryCombination(a)<<endl<<endl;

	int cans = tryCombination(a);
	if(cans<cnt && cans>=0){
		return query(MID+1, r, sttate);
	}
	else return query(l, MID, sttate);
}

void exploreCave(int N) {
	n = N;
	int ans[n] = {};
	for(int i=0;i<n;i++){
		int a[n] = {};
		for(int j=0;j<n;j++) a[j] = (used[j] ? state[j] : 0);
		int correct_state = 1;
		cnt = i+1;
		//cout<<"============ "<<cnt<<" ==============\n";

		//cout<<"STATE DET: ";
		//for(int j=0;j<n;j++) cout<<a[j]<<" ";
		//cout<<endl;
		//cout<<tryCombination(a)<<endl<<endl;

		if(tryCombination(a)>=cnt || tryCombination(a)==-1) correct_state=0;
		//cout<<"STATE: "<<correct_state<<endl;
		int pos = query(0, n-1, correct_state);
		ans[pos] = i;
		state[pos] = correct_state;
		used[pos] = true;
	}
	answer(state, ans);
}

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