Submission #169653

#	Time	Username	Problem	Language	Result	Execution time	Memory
169653		anubhavdhar	Cave (IOI13_cave)	C++14	100 / 100	1189 ms	640 KiB

cave

#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;
	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;
}
*/

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:52:9: warning: unused variable 'k' [-Wunused-variable]
  ll i,j,k,lo,hi,a,b,c,t,mid;
         ^
cave.cpp:52:21: warning: unused variable 'c' [-Wunused-variable]
  ll i,j,k,lo,hi,a,b,c,t,mid;
                     ^

• Subtask 1: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24