Submission #1218459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218459		nickolasarapidis	Cave (IOI13_cave)	C++20	0 / 100	78 ms	324 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;

void solve(int l, int r){
	if(l == r){
		S[l] = 1;
		int f = tryCombination(S);
		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++){
		S[i] = 1;
		int f = tryCombination(S);
		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);
	solve(0, N - 1);
	answer(S, D);
}

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