| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1316898 | exoworldgd | 동굴 (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include"cave.h"
#define ll long long
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
void exploreCave(int n){
int s[n],d[n];
bool v[n];
for(int i=0;i<n;i++)s[i]=0,d[i]=i,v[i]=0;
auto ok=[&](int x,int r,int f)->bool{
int t[n];
for(int i=0;i<n;i++)t[i]=s[i];
if(f)for(int i=0;i<=r;i++)if(!v[i])t[i]^=1;
elsefor(int i=r+1;i<n;i++)if(!v[i])t[i]^=1;
return tryCombination(t)!=x;
};
for(int i=0;i<n;i++){
int pos=tryCombination(s);
bool lk=0;
if(pos==i)lk=1;
int l=0,r=n-1,ans=0;
while(l<=r){
int m=(l+r)>>1;
if(ok(i,m,lk))ans=m,r=m-1;
else l=m+1;
}
s[ans]^=lk,v[ans]=1,d[ans]=i;
}
answer(s,d);
}
