Submission #163984

#	Time	Username	Problem	Language	Result	Execution time	Memory
163984		nabilervatra	Cave (IOI13_cave)	C++14	100 / 100	1373 ms	640 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
int l,r,arr[5005],ret,mid,buka,tmp,ans[5005],jwb[5005],n;
pair<int,int> fix[5005];
bool udah[5005];
void exploreCave(int N) {
	n=N;
	for(int i =0;i<n;i++){
		l = 0;
		r = n-1;
		
		for(int j =0;j<n;j++){
			if(!udah[j])arr[j] = 1;
		}
		ret = tryCombination(arr);
		if(ret == i)buka = 0;
		else buka = 1;
		// if(i==1)cout<<buka<<endl;
		while(l<=r){
			int mid = (l+r)/2;
			for(int j =0;j<n;j++){
				if(!udah[j])arr[j] = buka^1;
			}
			for(int j =l;j<=mid;j++){
				if(!udah[j])arr[j] = buka;
			}
			ret = tryCombination(arr);
			// if(i==1)cout<<ret<<endl;
			if(ret==i)l = mid+1;
			else {
				tmp = mid;
				r = mid-1;
			}
		}
		// fix[tmp].fi = buka;
			// cout<<tmp<<endl;
		ans[tmp]= i;
		arr[tmp] = buka;
		udah[tmp]=1;
	}

	answer(arr,ans);
}

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