Submission #1204091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204091		MuhammadSaram	Park (JOI17_park)	C++20	In queue	0 ms	0 KiB

park

#include "park.h"
#include <bits/stdc++.h>

using namespace std;

map<pair<int,int>,bool> mp;

bool comp(int a,int b)
{
	if (!mp.count({a,b}))
	{
		int on[1400]={};
		for (int i=0;i<1400;i++)
			on[i]=1;
		on[a]=0;
		if (Ask(0,b,on))
			mp[{a,b}]=0,mp[{b,a}]=1;
		else
			mp[{a,b}]=1,mp[{b,a}]=0;
	}
	return mp[{a,b}];
}

void Detect(int T, int n){
	int on[1400]={};
	if (T==1)
	{
		for (int i=0;i<n;i++)
			for (int j=i+1;j<n;j++)
			{
				on[i]=on[j]=1;
				if (Ask(i,j,on))
					Answer(i,j);
				on[i]=on[j]=0;
			}
		return;
	}
	else if(T==2)
	{
		if (n==2)
		{
			Answer(0,1);
			return;
		}
		vector<int> v;
		for (int i=1;i<n-1;i++)
			v.push_back(i);
		sort(v.begin(),v.end(),comp);
		Answer(0,v[0]);
		Answer(v.back(),n-1);
		for (int i=0;i+1<v.size();i++)
			Answer(min(v[i],v[i+1]),max(v[i],v[i+1]));
	}
	vector<int> dep[9];
	dep[0]={0};
	int par[n];
	bool vis[n]={};
	for (int d=1;d<=9;d++)
	{
		for (int j=d-1;j>=0;j--)
			for (int u:dep[j])
				on[u]=1;
		for (int i=1;i<n;i++)
			if (!vis[i])
			{
				on[i]=1;
				if (Ask(0,i,on))
					dep[d].push_back(i),vis[i]=1;
				on[i]=0;
			}
		for (int i=0;i<n;i++) on[i]=0;
		for (int u:dep[d])
		{
			int s=-1,e=dep[d-1].size()-1;
			while (s+1<e)
			{
				int mid=(s+e)/2;
				on[0]=on[u]=1;
				for (int j=0;j<=mid;j++)
				{
					int v=dep[d-1][j];
					while (v)
						on[v]=1,v=par[v];
				}
				if (Ask(0,u,on))
					e=mid;
				else
					s=mid;
				for (int i=0;i<n;i++) on[i]=0;
			}
			par[u]=dep[d-1][e];
			Answer(min(par[u],u),max(par[u],u));
		}
	}
}