| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 169652 | anubhavdhar | Cave (IOI13_cave) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long int
#define FOR(i,N) for(i=0;i<N;i++)
#define FORe(i,N) for(i=1;i<=N;i++)
#define FORr(i,a,b) for(i=a;i<b;i++)
#define ii pair<ll,ll>
#define vi vector<ll>
#define vii vector<ii>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
using namespace std;
#include "cave.h"
/*
const ll MAXN = 1e5+5;
const ll INF = 1e17 + 9;
const ll MOD = 1e9 + 7;
const ll INT_BITS = 31;
const ll LOGN = 17;
*/
#define MAXN 200005
/*
inline int tryCombination(vector<int> v)
{
ll i;
cout<<"asking\n";
FOR(i,v.size())
cout<<v[i]<<" ";
cout<<endl;
cin>>i;
return i;
}
inline void answer(vector<int> d,vector<int> s)
{
ll i;
cout<<"\n\n\ncorrect positions of switch\n";
FOR(i,d.size())
cout<<d[i]<<" ";
cout<<"\nswitch no to door is\n";
FOR(i,s.size())
cout<<s[i]<<" ";
}
*/
void exploreCave(int N)
{
ll i,j,k,lo,hi,a,b,c,t,mid;
vector<int> switch_of_door(N),combination(N),correct(N),door_of_switch(N);
FOR(i,N)
{
switch_of_door[i] = i;
door_of_switch[i] = i;
combination[i] = correct[i] = 0;
}
//
FOR(i,N)
{
//cout<<"starting to find switch of door "<<i<<endl;
lo = i;
hi = N-1;
FOR(j,N)
{
b = switch_of_door[j];
if(j<i)
{
//cout<<"switch_of_door "<<j<<" i.e. switch "<<b<<" is before "<<i<<endl;
combination[b] = correct[b];
}
else
{
//cout<<"switch_of_door "<<j<<" i.e. switch "<<b<<" is >= "<<i<<"so combination["<<b<<"] = 0"<<endl;
combination[b] = 0;
}
}
t = (tryCombination(combination) == i);
//cout<<"got t = "<<t<<endl;
if (i == N-1)
{
correct[switch_of_door[i]] = t;
break;
}
while(lo < hi)
{
//cout<<"in while loop with lo = "<<lo<<" and hi = "<<hi<<endl;
mid = (lo + hi)/2;
FOR(j,N)
{
b = switch_of_door[j];
if(j < i)
{
//cout<<"switch_of_door "<<j<<" i.e. switch "<<b<<" is before "<<i<<endl;
combination[b] = correct[b];
continue;
}
if(j < lo or j > hi)
{
//cout<<"switch_of_door "<<j<<" i.e. switch "<<b<<" is out of range "<<lo<<" "<<hi<<endl;
combination[b] = t;
continue;
}
if(j <= mid)
{
//cout<<"switch_of_door "<<j<<" i.e. switch "<<b<<" is <= "<<mid<<" setting that to "<<t<<endl;
combination[b] = t;
}
else
{
//cout<<"switch_of_door "<<j<<" i.e. switch "<<b<<" is > "<<mid<<" setting that to "<<1-t<<endl;
combination[b] = 1 - t;
}
}
a = tryCombination(combination);
if (a == i)
lo = mid+1;
else
hi = mid;
}
a = switch_of_door[i];
b = switch_of_door[lo];
switch_of_door[i] = b;
door_of_switch[b] = i;
//cout<<"switch_of_door "<<i<<" i.e. switch "<<switch_of_door[i]<<" has correct value "<<t<<endl;
correct[switch_of_door[i]] = t;
if (i == N-1)
{
//cout<<"thats it\n";
break;
}
switch_of_door[lo] = a;
door_of_switch[a] = lo;
//cout<<"making switch_of_door "<<lo<<" = switch "<<a<<endl;
}
answer(correct,door_of_switch);
}
/*
int main()
{
ll N,i;
cin>>N;
exploreCave(N);
return 0;
}
*/