Submission #99364

#	Time	Username	Problem	Language	Result	Execution time	Memory
99364		nad312	Cave (IOI13_cave)	C++17	100 / 100	430 ms	564 KiB

cave

#include <cave.h>
#include<bits/stdc++.h>
using namespace std;
typedef int lli;

const lli N=5009, inf=1e9;
lli n, a[N], query[N], com[N], pos[N];
lli Ask()
{
	lli k=tryCombination(query);
	if(k==-1)
	{
		return inf;
	}
	return k;
}
void Find(lli x)
{
	vector<lli> p;
	for(int i=0;i<n;i++)
	{
		if(com[i]==-1)
		{
			query[i]=0;
			p.push_back(i);
		}
		else
		{
			query[i]=com[i];
		}
	}
	lli a=(Ask()>x), l=0, h=p.size()-1;
	while(l<h)
	{
		lli mid=(l+h)/2;
		for(int i=l;i<=mid;i++)
		{
			query[p[i]]=0;
		}
		for(int i=mid+1;i<=h;i++)
		{
			query[p[i]]=1;
		}
		if(Ask()>x)
		{
			if(a==1)
			{
				h=mid;
			}
			else
			{
				l=mid+1;
			}
		}
		else
		{
			if(a==1)
			{
				l=mid+1;
			}
			else
			{
				h=mid;
			}
		}
	}
	com[p[l]]=(a^1);
	pos[p[l]]=x;
}
void exploreCave(int m)
{
	n=m;
	fill_n(&com[0], sizeof(com)/sizeof(com[0]), -1);
	fill_n(&pos[0], sizeof(pos)/sizeof(pos[0]), -1);
	for(int i=0;i<n;i++)
	{
		Find(i);
	}
	answer(com, pos);
}

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