Submission #697191

#	Time	Username	Problem	Language	Result	Execution time	Memory
697191		amunduzbaev	Park (JOI17_park)	C++17	0 / 100	370 ms	604 KiB

park

#include "park.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif

mt19937 rng(chrono :: steady_clock :: now().time_since_epoch().count());
#define rnd(l, r) uniform_int_distribution<int>(l, r)(rng)

static int used[1400];
void Detect(int t, int n){
	auto ask = [&](int a, int b){
		if(a > b) swap(a, b);
		int ans = Ask(a, b, used);
		return ans;
	};
	
	auto Ans = [&](int i, int j){
		if(i > j) swap(i, j);
		//~ cout<<i<<" "<<j<<"\n";
		Answer(i, j);
	};
	
	vector<vector<int>> par(n);
	vector<int> sz(n);
	
	for(int i=1;i<n;i++){
		vector<int> tot(n - 1);
		iota(tot.begin(), tot.end(), 1);
		tot.erase(tot.begin() + i - 1, tot.begin() + i);
		shuffle(tot.begin(), tot.end(), rng);
		vector<int>& rem = par[i];
		//~ cout<<"here : "<<i<<"\n";
		while(true){
			int l = 0, r = tot.size();
			
			while(l < r){
				int m = (l + r) >> 1;
				for(int j=0;j<m;j++){
					used[tot[j]] = 1;
				} used[0] = used[i] = 1;
				for(auto x : rem) used[x] = 1;
				
				//~ for(int i=0;i<n;i++) cout<<used[i]<<" ";
				//~ cout<<" : "<<ask(0, i)<<"\n";
				
				if(ask(0, i)){
					r = m;
				} else {
					l = m + 1;
				}
				
				for(int j=0;j<m;j++){
					used[tot[j]] = 0;
				} used[0] = used[i] = 0;
				for(auto x : rem) used[x] = 0;
			}
			
			//~ for(auto x : tot) cout<<x<<" ";
			//~ cout<<"\n";
			//~ cout<<l<<"\n";
			
			if(!l){
				break;
			}
			while((int)tot.size() > l){
				tot.pop_back();
			}
			rem.push_back(tot.back());
			tot.pop_back();
		}
		
		sz[i] = par[i].size();
	}
	
	//~ for(int i=1;i<n;i++){
		//~ cout<<i<<" : ";
		//~ for(auto x : par[i]) cout<<x<<" ";
		//~ cout<<"\n";
	//~ }
	
	vector<int> p(n - 1);
	iota(p.begin(), p.end(), 1);
	sort(p.begin(), p.end(), [&](int i, int j){
		return sz[i] < sz[j];
	});
	//~ for(auto x : p) cout<<x<<" ";
	//~ cout<<"\n";
	for(int i=0;i+1<n;i++){
		int x = p[i];
		if(!sz[x]){
			par[x].push_back(x);
			sort(par[x].begin(), par[x].end());
			Ans(0, x);
			continue;
		}
		sort(par[x].begin(), par[x].end());
		for(int j=0;j<i;j++){
			if(par[p[j]] == par[x]){
				//~ cout<<p[j]<<" "<<x<<"\n";
				//~ for(auto x : par[p[j]]) cout<<x<<" ";
				//~ cout<<"\n";
				//~ for(auto x : par[x]) cout<<x<<" ";
				//~ cout<<"\n";
				Ans(p[j], x);
			}
		}
		//~ for(int i=1;i<n;i++){
			//~ cout<<i<<" : ";
			//~ for(auto x : par[i]) cout<<x<<" ";
			//~ cout<<"\n";
		//~ }
		par[x].push_back(x);
		sort(par[x].begin(), par[x].end());
	}
}


/*

1
7
6
0 4
4 3
3 1
1 2
2 5
5 6

1
8
7
0 1
0 2
0 6
1 3
1 4
1 5
6 7

*/

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