제출 #593394

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
593394		shezitt	동굴 (IOI13_cave)	C++14	12 / 100	416 ms	596 KiB

cave

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

using namespace std;

const int mxN = 5e3+5;
bool done[mxN];

bool open(int q, int i){
	if(q == -1){
		return 1;
	}
	return q > i;
}

void exploreCave(int N) {
	int a[N], b[N];
	for(int i=0; i<N; ++i){
		b[i] = -1;
	}
	for(int i=0; i<N; ++i){
		for(int j=0; j<N; ++j){
			if(b[j] == -1){
				a[j] = 0;
			}
		}
		bool p = !open(tryCombination(a), i);
		int l = 0, r = N-1, ans = -1;
		while(l <= r){
			int mid = (l+r)/2;
			for(int j=0; j<N; ++j){
				if(b[j] == -1){
					if(j >= l && j <= mid){
						a[j] = p;
					} else {
						a[j] = !p;
					}
				}
			}
			if(open(tryCombination(a), i)){
				ans = mid;
				r = mid-1;
			} else {
				l = mid+1;
			}
		}
		assert(ans != -1);  
		b[ans] = i;
		a[i] = p;
	}
	answer(a, b);
}

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