oj.uz

Submission #320626

# Submission time Handle Problem Language Result Execution time Memory
320626 2020-11-09T09:39:27 Z arnold518 Park (JOI17_park) C++14
27 / 100
 132 ms 628 KB 
#include "park.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1500;

int T, N;
int P[MAXN+10];

int query(int A, int B)
{
	return Ask(A, B, P);	
}

void answer(int A, int B)
{
	if(A>B) swap(A, B);
	Answer(A, B);
}

bool vis[MAXN+10];

void solve(vector<int> V1, vector<int> V2)
{
	if(V2.empty()) return;
	if(V1.size()==1)
	{
		for(auto it : V2)
		{
			answer(V1[0], it);
		}
		return;
	}

	vector<int> L1, R1, L2, R2;
	int mid=V1.size()/2;
	for(int i=0; i<mid; i++) L1.push_back(V1[i]);
	for(int i=mid; i<V1.size(); i++) R1.push_back(V1[i]);

	for(auto it : L1) P[it]=1;
	for(auto it : V2)
	{
		P[it]=1;
		if(query(0, it)) L2.push_back(it);
		else R2.push_back(it);
		P[it]=0;
	}
	for(auto it : L1) P[it]=0;

	solve(L1, L2);
	solve(R1, R2);
}

void Detect(int _T, int _N)
{
	T=_T; N=_N;

	int cnt=1;
	P[0]=1; vis[0]=1;

	vector<vector<int>> VV;
	VV.push_back({0});
	while(cnt<N)
	{
		vector<int> V;
		for(int i=0; i<N; i++)
		{
			if(vis[i]) continue;
			P[i]=1;
			if(query(0, i))  V.push_back(i);
			P[i]=0;
		}

		for(auto it : VV.back()) P[it]=0;
		solve(VV.back(), V);
		for(auto it : VV.back()) P[it]=1;

		for(auto it : V)
		{
			cnt++;
			P[it]=1;
			vis[it]=1;
		}
		VV.push_back(V);

	}



}

Compilation message

park.cpp: In function 'void solve(std::vector<int>, std::vector<int>)':
park.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for(int i=mid; i<V1.size(); i++) R1.push_back(V1[i]);
      |                 ~^~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 364 KB Wrong Answer[5]
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 488 KB Output is correct
2 Correct 96 ms 492 KB Output is correct
3 Correct 85 ms 492 KB Output is correct
4 Correct 50 ms 492 KB Output is correct
5 Correct 90 ms 492 KB Output is correct
6 Correct 75 ms 492 KB Output is correct
7 Correct 70 ms 484 KB Output is correct
8 Correct 85 ms 612 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 364 KB Output is correct
2 Incorrect 78 ms 484 KB Wrong Answer[5]
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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