# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1208615 | pera | 동굴 (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include "caves.h"
using namespace std;
void exploreCave(int N) {
int S[N] , D[N] , W[N];
memset(S , 0 , sizeof(S));
memset(W , 0 , sizeof(W));
vector<int> v(N);
iota(v.begin() , v.end() , 0);
for(int i = 0;i < N;i ++){
int col = (tryCombination(W) == i);
for(int x : v){
W[x] = (col ^ 1);
}
int l = 0 , r = (int)v.size() - 1 , ans = -1;
while(l <= r){
int m = (l + r) / 2;
for(int j = 0;j <= m;j ++){
W[v[j]] = col;
}
int C = tryCombination(W);
if(C == -1 || C > i){
ans = v[m];
r = m - 1;
}else{
l = m + 1;
}
for(int j = 0;j <= m;j ++){
W[v[j]] = (col ^ 1);
}
}
v.erase(find(v.begin() , v.end() , ans));
S[ans] = col;
W[ans] = col;
D[ans] = i;
for(int x : v){
W[x] = 0;
}
}
answer(S , D);
return;
}