Submission #593393

#	Time	Username	Problem	Language	Result	Execution time	Memory
593393		shezitt	Cave (IOI13_cave)	C++14	12 / 100	394 ms	628 KiB

cave

#include "cave.h"
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cassert>
#include <set>

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){
		a[i] = 0, 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 = 1;
		if(open(tryCombination(a), i)){
			p = !p;
		}
		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