Submission #339923

#	Time	Username	Problem	Language	Result	Execution time	Memory
339923		Kerim	Cave (IOI13_cave)	C++17	51 / 100	608 ms	620 KiB

cave

#include "cave.h"
#include "bits/stdc++.h"
using namespace std;
void exploreCave(int n) {
	vector<int>a(n),b(n),c(n);
	for(int i=0;i<n;i++)a[i]=-1;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(~a[j])c[j]=a[j];
			else c[j]=0;
		}
		int val=(tryCombination(c.data())==i);
		int st=0,en=n-1;
		while(st+1<en){
			int mid=(st+en)>>1;
			for(int j=0;j<n;j++){
				if(~a[j])c[j]=a[j];
				else c[j]=val^(j<mid);	
			}
			if(tryCombination(c.data())==i) en=mid;
			else st=mid;
		}
		for(int j=0;j<n;j++){
			if(~a[j])c[j]=a[j];
			else c[j]=val^(j<en);	
		}
		if(tryCombination(c.data())!=i)
			a[en]=val,b[en]=i;
		else a[st]=val,b[st]=i;
	}
	answer(a.data(),b.data());
}

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