# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1216790 | takoshanava | Cave (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
bool vis[5002];
int n, R[5002], D[5002];
void change( int i, int j ){
for( ; i <= j; i++ )
if( !vis[i] )
R[i] = ( R[i] + 1 ) % 2;
}
void exploreCave(int N) {
n = N;
for(int i = 0; i < n; i++){
int s, ps, r, ll, rr, m;
r = tryCombination( n, R );
if(r > i or r == -1){
s = 0;
}else{
s = 1;
}
ll = 0; rr = n - 1;
while(ll != rr){
m = (ll + rr) / 2;
change(ll, m);
r = tryCombination(n, R);
if(r > i or r == -1){
ps = 0;
}else{
ps = 1;
}
change(ll, m);
if(ps != s) rr = m;
else ll = m + 1;
}
D[ll] = i;
R[ll] = s;
vis[ll] = 1;
}
answer(n, R, D);
}