# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1218458 | nickolasarapidis | Cave (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#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 explore_cave(int N){
memset(S, 0, sizeof(S));
memset(B, 0, sizeof(B));
first = tryCombination(S);
solve(0, N - 1);
answer(S, D);
}