Submission #588261

#	Time	Username	Problem	Language	Result	Execution time	Memory
588261		IvanJ	Cave (IOI13_cave)	C++17	100 / 100	796 ms	460 KiB

cave

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

using namespace std;

const int maxn = 5005;

int n;
int S[maxn], D[maxn];

void exploreCave(int N) {
    n = N;
    memset(D, -1, sizeof D);
    for(int i = 0;i < n;i++) {
		for(int j = 0;j < n;j++) if(D[j] == -1) S[j] = 0;
		int x = tryCombination(S), open = 1;
		if(x > i || x == -1) open = 0; 
		int lo = 0, hi = n - 1, ans = -1;
		while(lo <= hi) {
			int mid = (lo + hi) / 2;
			for(int j = 0;j < n;j++) {
				if(D[j] != -1) continue;
				if(lo <= j && j <= mid) S[j] = open;
				else S[j] = !open;
			}
			int y = tryCombination(S);
			if(y > i || y == -1) ans = mid, hi = mid - 1;
			else lo = mid + 1;
		}
		D[ans] = i;
		S[ans] = open;
	}
	answer(S, D);
}

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