Submission #154825

#	Time	Username	Problem	Language	Result	Execution time	Memory
154825		Nightlight	Cave (IOI13_cave)	C++14	0 / 100	739 ms	484 KiB

cave

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

bool found[70005];int ketemu;
bool ANS[70005];
int longs;

int binser1(){
	int l = 0, r = longs-1, res = -1;
	while(l <= r){
		int mid = (l+r)/2;
		int tmp[longs];
		for(int i = 0; i < longs; i++){
			if(found[i])tmp[i] = ANS[i];
			else tmp[i] = (l <= i && mid >= i) ? 1 : 0;
		}
		if(tryCombination(tmp) > ketemu){
			r = mid+1;
			res = mid;
		}else l = mid;
	}
	return res;
}

int binser2(){
	int l = 0, r = longs-1, res = -1;
	while(l <= r){
		int mid = (l+r)/2;
		int tmp[longs];
		for(int i = 0; i < longs; i++){
			if(found[i])tmp[i] = ANS[i];
			else tmp[i] = (l <= i && mid >= i) ? 0 : 1;
		}
		if(tryCombination(tmp) > ketemu){
			r = mid+1;
			res = mid;
		}else l = mid;
	}
	return res;
}


void exploreCave(int N) {
	int Switch[N];
	int door[N];
	longs = N;
	for(ketemu = 0; ketemu < N; ketemu++){
		int res = binser1();
		if(res != -1){
			door[ketemu] = res;
			ANS[res] = 1;
			found[res] = 1;
			Switch[res] = 1;
			continue;
		}
		res = binser2();
		door[ketemu] = res;
		Switch[res] = 1;
		found[res] = 1;
	}
    answer(Switch, door);
}

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