Submission #1218767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218767		nickolasarapidis	Cave (IOI13_cave)	C++20	0 / 100	1 ms	328 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5000;

int S[MAXN], D[MAXN], B[MAXN]; // 0 up 1 down

int first, M;

void finish(){
	for(int i = 0; i < M; i++){
		if(B[i] == 1) continue;
		S[i] = 1;
		int f = tryCombination(S);
		D[i] = f;
		S[i] = 0;
	}
	answer(S, D);
}

void solve(int l, int r){
	if(l == r){
		S[l] = 1;
		int f = tryCombination(S);
		if(f == -1){
			finish();
		}
		if(f < first){
			S[l] = 0;
			B[l] = 1;
			D[l] = f;
		}
		if(f > first){
			B[l] = 1;
			D[l] = first;
			first = f;
		}
		if(f == first){
			S[l] = 0;
		}
		return;
	}
	int m = (l + r)/2;
	solve(l, m);
	solve(m + 1, r);
	for(int i = l; i <= r; i++){
		if(B[i]) continue;
		S[i] = 1;
		int f = tryCombination(S);
		if(f == -1){
			finish();
		}
		if(f < first){
			S[i] = 0;
			B[i] = 1;
			D[i] = f;
		}
		if(f > first){
			B[i] = 1;
			D[i] = first;
			  first = f;
		}
		if(f == first){
			S[i] = 0;
		}
	}
	return;
}

void exploreCave(int N){
	memset(S, 0, sizeof(S));
	memset(B, 0, sizeof(B));
	first = tryCombination(S);
	if(first == -1) finish();
	M = N;
	solve(0, N - 1);
}

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