Submission #306372

#	Time	Username	Problem	Language	Result	Execution time	Memory
306372		tengiz05	Cave (IOI13_cave)	C++17	0 / 100	122 ms	464 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int s[6000];
int d[6000];
int used[6000];
int last;
bool First;
bool check(int l, int r){
	for(; l <= r;l++){
		if(used[l] == 1)continue;
		s[l] = 1;
	}
	int temp1 = tryCombination(s);
	for(; l <= r;l++){
		if(used[l] == 1)continue;
		s[l] = 0;
	}
	int temp2 = tryCombination(s);
	if(temp1 >= last){
		First = 1;
		return temp2 >= last;
	}else {
		First = 0;
		return temp1 >= last;
	}
}
void exploreCave(int n) {
	for(int door = 0; door < n; door ++ ){
		last = door+1;
		int l=0, r=n;
		while(l+1 < r){
			int mid = (l+r)/2;
			if(check(l, mid)){
				r = mid;
			}else {
				l = mid;
			}
		}
		d[door] = l;
		s[door] = First;
		used[door] = 1;
	}
	answer(s, d);
}
/*

4
1 1 1 0
3 1 0 2

*/

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