Submission #1218504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218504		nickolasarapidis	동굴 (IOI13_cave)	C++20	13 / 100	7 ms	580 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 solve(int l, int r){
	if(l == r){
		S[l] = 1;
		int f = tryCombination(S);
		if(f == -1) f = M;
		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) f = M;
		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) first = N;
	M = N;
	solve(0, N - 1);
	int A[N], B[N];
	for(int i = 0; i < N; i++){
		A[i] = S[i];
		B[i] = D[i];
	}
	answer(A, B);
}

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