# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1257269 | FernandoJC07 | 동굴 (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "greader.h"
#include "cave.h"
#define vi vector<int>
#define vii vector<vi>
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vpii vector<pii>
#define forn(i, n) for(int i = 0; i<n; ++i)
#define For(i, a, n) for(int i = a; i<n; ++i)
using namespace std;
void exploreCave(int N){
int S[N], D[N];
forn(i, N) { S[i] = D[i] = -1;}
forn(door, N){
int q[N];
vi oo;
forn(i, N){
if(S[i] != -1) q[i] = S[i];
else {q[i] = 0; oo.pb(i);}
}
int val1 = tryCombination(q);
int s;
if(val1 == door) s = 1; else s= 0;
int l = 0, r = oo.size()-1;
while(r>l){
int mid = l + (r-l)/2;
for(int x: oo) q[x] = 1-s;
For(i, l, mid+1){
q[oo[i]] = s;
}
//dbg(mid);
int val2 = tryCombination(q);
//dbg(val2);
if(val2 == door) l=mid+1;
else r = mid;
}
D[oo[l]] = door;
S[oo[l]] = s;
/*dbg(oo[l]);
dbg(S[oo[l]]);
dbg(D[oo[l]]);*/
}
answer(S, D);
}