# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1177495 | tegshzaya | Cave (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include "cave.h"
#include<bits/stdc++.h>
#define ss second
#define ff first
#define pb push_back
void exploreCave(int N){
int a[N+5],b[N+5],c[N+5];
for(int i=0;i<N;i++){
int s[N+5];
for(ll j=0;j<N;j++){
if(c[j]!=0) s[j]=a[j];
else s[j]=0;
}
int x=tryCombination(s);
int t=1;
if(x==-1 || x>i) t=0;
vector<ll> v;
for(int j=0;j<n;j++){
if(c[j]==0) v.pb(j);
}
while(v.size()>1){
for(int j=0;j<n;j++){
if(c[j]!=0) s[j]=a[j];
else s[j]=0;
}
vector<ll> v1,v2;
int u=v.size();
for(int j=0;j<u/2;j++){
v1.pb(v[j]);
s[v[j]]=(1-t);
}
for(int j=u/2;j<u;j++){
v2.pb(v[j]);
s[v[j]]=(1-t);
}
x=tryCombination(s);
if(x==-1 || x>i) v=v1;
else v=v2;
}
c[v.back()]=1;
a[v.back()]=t;
b[v.back()]=i;
}
int s[N+5],k[N+5];
for(int i=0;i<N;i++){
s[i]=a[i];
k[i]=b[i];
}
answer(s,k);
}