Submission #26454

#	Time	Username	Problem	Language	Result	Execution time	Memory
26454		pacu	Park (JOI17_park)	C++98	47 / 100	216 ms	2176 KiB

park

#include "park.h"
#include <cstdlib>
#include <vector>
using namespace std;

static int place[1400];
int nNodes;

void clear()
{
	for(int j=0;j<nNodes;j++)
		place[j] = 0;
}

void fill()
{
	for(int j=0;j<nNodes;j++)
		place[j] = 1;
}

void ansEdge(int a,int b)
{
	if(a>b) swap(a,b);
	Answer(a,b);
}

int question(int a,int b,int p[])
{
	if(a>b) swap(a,b);
	return Ask(a,b,p);
}

void solveRange(int l,int r,vector<int> lst)
{
	if(lst.size()==0)
	{
		ansEdge(l,r);
		return;
	}
	int mid = lst[rand()%lst.size()];
	vector<int> lList,rList;
	for(int j=0;j<lst.size();j++) if(lst[j]!=mid)
	{
		fill();
		place[lst[j]] = 0;
		if(question(l,mid,place)) rList.push_back(lst[j]);
		else lList.push_back(lst[j]);
	}
	solveRange(l,mid,lList);
	solveRange(mid,r,rList);
}

vector<int> d[10];
int seen[1400];
int depth[1400];

void Detect(int T,int N)
{
	nNodes = N;
	if(T==1)
	{
		for(int i=0;i<N;i++)
			for(int j=i+1;j<N;j++)
			{
				clear();
				place[i] = place[j] = 1;
				if(Ask(i,j,place))
					ansEdge(i,j);
			}
	}
	if(T==2)
	{
		vector<int> lst;
		for(int i=1;i<N-1;i++)
			lst.push_back(i);
		solveRange(0,N-1,lst);
	}
	if(T==3)
	{
		d[0].push_back(0);
		seen[0] = 1;
		depth[0] = 0;
		for(int k=1;k<10;k++)
		{
			for(int i=0;i<N;i++) if(seen[i]==0)
			{
				clear();
				for(int j=0;j<N;j++)
					if(seen[j]==1)
						place[j] = 1;
				place[i] = 1;
				if(question(0,i,place))
					seen[i] = 2;
			}
			for(int i=0;i<N;i++)
				if(seen[i]==2)
				{
					d[k].push_back(i);
					seen[i] = 1;
					depth[i] = k;
				}
		}
		for(int i=1;i<N;i++)
		{
			int k = depth[i]-1;
			if(k==0)
			{
				ansEdge(0,i);
				continue;
			}
			int low = 0;
			int high = d[k].size()-1;
			while(low != high)
			{
				int mid = (low+high)/2;
				clear();
				for(int j=0;j<N;j++) if(depth[j]<k) place[j] = 1;
				for(int j=low;j<=mid;j++) place[d[k][j]] = 1;
				place[i] = 1;
				if(question(0,i,place)) high = mid;
				else low = mid+1;
			}
			ansEdge(d[k][low],i);
		}
	}
}

Compilation message (stderr)

park.cpp: In function 'void solveRange(int, int, std::vector<int>)':
park.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<lst.size();j++) if(lst[j]!=mid)
               ^

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 0 / 30
• Subtask 5: 0 / 23