제출 #306407

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
306407		tengiz05	동굴 (IOI13_cave)	C++17	100 / 100	1324 ms	760 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int s[6000];
int d[6000];
int used[6000];
int n, color;
int check(int l, int r){
	int i;
	for(i=0;i<n;i++){
		if(used[i] == 1)continue;
		s[i] = 0;
	}for(i=l;i<=r;i++){
		if(used[i] == 1)continue;
		s[i] = 1;
	}
	return tryCombination(s);
}
void exploreCave(int N) {
	n = N;
	for(int door = 0; door < n; door ++){
		color = tryCombination(s);
		if(color == -1){
			color = n;
		}if(color >= door+1)color = 0;
		else color = 1;
		int l=0, r=n-1;
		while(l < r){
			int mid = (l+r)/2;
			int ch = check(l, mid);
			if(((color == 1)^(ch == door))){
				r = mid;
			}else {
				l = mid+1;
			}
		}//cout << l << '\n';
		used[l] = 1;
		s[l] = color;
		d[l] = door;
		for(int i=0;i<n;i++){
			if(used[i])continue;
			s[i] = 0;
		}
	}
	answer(s, d);
}
/*

4
1 1 1 0
3 1 0 2

*/

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