oj.uz

Submission #26454

# Submission time Handle Problem Language Result Execution time Memory
26454 2017-06-30T21:58:21 Z pacu Park (JOI17_park) C++
47 / 100
 216 ms 2176 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2044 KB Output is correct
2 Correct 9 ms 2044 KB Output is correct
3 Correct 9 ms 2044 KB Output is correct
4 Correct 9 ms 2044 KB Output is correct
5 Correct 9 ms 2044 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 2176 KB Output is correct
2 Correct 129 ms 2176 KB Output is correct
3 Correct 133 ms 2176 KB Output is correct
4 Correct 169 ms 2044 KB Output is correct
5 Correct 216 ms 2176 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 2044 KB Output is correct
2 Correct 193 ms 2044 KB Output is correct
3 Correct 196 ms 2044 KB Output is correct
4 Correct 129 ms 2044 KB Output is correct
5 Correct 186 ms 2044 KB Output is correct
6 Correct 179 ms 2044 KB Output is correct
7 Correct 143 ms 2044 KB Output is correct
8 Correct 189 ms 2044 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2044 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2044 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -