Submission #823285

#	Time	Username	Problem	Language	Result	Execution time	Memory
823285		ThylOne	Cave (IOI13_cave)	C++14	100 / 100	364 ms	692 KiB

cave

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

using namespace std;
typedef pair<int,int> pii;
void fillRec(int rec[],int N,int val){
	for(int i=0;i<N;i++){
		rec[i]=val;
	}
}
int ask(int rec[]){
	int re = tryCombination(rec);
	if(re==-1){
		re=5042;
	}
	return re;
}
void exploreCave(int N) {
	vector<pii> finded;
	int order[N];
	int rec[N];
	for(int iPorte=0;iPorte<N;iPorte++){
		//find the levier position
		int Val;
		fillRec(rec,N,0);
		for(auto p:finded){
			rec[p.first]=p.second;
		}
		if(ask(rec)>iPorte){
			Val=0;
		}else{
			Val=1;
		}
		int inf=0;
		int sup=N-1;
		while(inf<sup){
			int mid = (inf+sup)/2;
			fillRec(rec,N,!Val);
			for(int i=inf;i<=mid;i++){
				rec[i]=Val;
			}
			for(auto p:finded){
				rec[p.first]=p.second;
			}
			if(ask(rec)>iPorte){
				//left
				sup=mid;
			}else{
				//right
				inf=mid+1;
			}
		}
		order[inf]=iPorte;
		finded.push_back({inf,Val});
	}
	int biny[N];
	for(auto p:finded){
		biny[p.first]=p.second;
	}
    answer(biny,order);
}

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