# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1217863 | lukasuliashvili | Cave (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include"cave.h".
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fs first
#define sc second
#define rep(i,a,b) for(int i=a; i<b; i++)
void exploreCave(int N){
int N1=2*1e6+5;
int fix[N],ans[N],s[N];
rep(i,0,N){fix[i]=-1;ans[i]=-1;}
// ans[j] --> j chamrtvelistvis romeli karia
// fix[i] i karistvis 1 ia tu -1
for(int i=0; i<N; i++){
rep(j,0,N){
if(ans[j]!=-1){
s[j]=fix[ans[j]];
}
else{
s[j]=0;
}
}
int last=tryCombination(s);
if( last<=i and last!=-1){
fix[i]=1;
}
else{
fix[i]=0;
}
int l=0;
int r=N-1;
while(l<=r){
if(l==r){
ans[l]=i;
break;
}
int mid=(l+r)/2;
rep(j,0,l){
if(ans[j]!=-1){
s[j]=fix[ans[j]];
}
else{
s[j]=(fix[i]^1);
}
}
rep(j,l,mid+1){
if(ans[j]!=-1){
s[j]=fix[ans[j]];
}
else{
s[j]=fix[i];
}
}
rep(j,mid+1,N){
if(ans[j]!=-1){
s[j]=fix[ans[j]];
}
else{
s[j]=(fix[i]^1);
}
}
tryCombination()
cin>>last;
if(last<=i and last!=-1){
l=mid+1;
}
else{
r=mid;
}
}
}
rep(i,0,N){
ans2[i]=fix[ans[i]];
}
answer(ans2,ans);
// ans2 ans
}