# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1164719 | tsengang | Cave (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include "cave.h"
using namespace std;
#define ll long long
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define ertunt return
#define vodka void
void exploreCave(int n){
int v[n] = {0};
int d[n] = {0};
bool vis[n] = {0};
for(int i = 0; i < n; i++){
vector<ll>s;
for(int j = 0 ; j < n; j++){
if(vis[j] == 0)s.pb(j);
}
for(int j = 0; j < s.size(); j++){
d[j] = 0;
}
int l = 0,r = s.size()-1;
int x = tryCombination(d);
ll q = 0,p = 1;
if(x == i)swap(q,p);
while(l < r){
int mid = (l+r)/2;
for(ll j = 0 ; j < s.size(); j++){
if(j <= mid)d[s[j]] = q;
else d[s[j]] = p;
}
int x = try_combination(d);
if(x == -1 or x > i){
r = mid;
}
else l = mid+1;
}
v[s[l]] = i;
d[s[l]] = q;
vis[s[l]] = true;
}
answer(d,v);
}