Submission #704780

#	Time	Username	Problem	Language	Result	Execution time	Memory
704780		uylulu	Park (JOI17_park)	C++14	0 / 100	9 ms	596 KiB

park

#include "park.h"
#include<bits/stdc++.h>
 
using namespace std;
 
const int N = 2000;
 
static int adj[1400];
bool vis[N + 1];

int n;
 
vector<pair<int,int>> res;
 
int help(int a,int b) {
	if(a > b) swap(a,b);
 
	return Ask(a,b,adj);
}
 
int ask(int a,int b) {
	adj[a] = true;
	adj[b] = true;

	int x = help(a,b);

	adj[a] = false;
	adj[b] = false;
	return x;
}

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

void init() {
	for(int i =0;i < n;i++) {
		adj[i] = false;
	}
}

void dfs(int s,vector<int> curr) {
	if(vis[s]) return;

	init();
	vector<int> nw;
	for(auto u : curr) {
		if(u != s) {
			nw.push_back(u);
		}
	}

	// if(s == 0) {
	// 	cout<<s<<endl;
	// 	for(auto u : nw) {
	// 		cout<<u<<" ";
	// 	}
	// 	cout<<endl;
	// }
	
	vis[s] = true;

	if(nw.size() == 0) return;

	if(ask(nw[0],s)) {

		for(auto u : nw) {

			init();

			// if(s == 1) {
			// 	cout<<s<<" "<<u<<" "<<ask(u,s)<<endl;
			// 	for(int i = 0;i < n;i++) {
			// 		cout<<i<<" "<<adj[i]<<endl;
			// 	}
			// } 

			if(ask(u,s)) {
				res.push_back({u,s});
				dfs(u,nw);
			}
		}
	} else {
		vector<int> tmp = nw,after;

		while(true) {
			int l = 0,r = tmp.size(),val = -1;

			while(l < r) {
				int mid = (l + r)/2;
				init();

				for(int i = 0;i <= mid;i++) {
					adj[tmp[i]] = true;
				}
				adj[s] = true;

				if(help(tmp[0],s)) {
					r = mid;
					val = tmp[mid];
				} else {
					l = mid + 1;
				}

			}

			if(val == -1) {
				break;
			}

			res.push_back({s,val});

			dfs(val,nw);

			after.clear();

			for(auto u : tmp) {
				if(u == val) continue;
				after.push_back(u);
			}
			tmp = after;
		}
	}
}
 
void Detect(int T, int N) {
	n = N;

	vector<int> curr;

	for(int i = 0;i < n;i++) {
		curr.push_back(i);
	}
	dfs(n - 1,curr);

	for(auto u : res) {
		// cout<<u.first<<" "<<u.second<<endl;

		ans(u.first,u.second);
	}
	
}

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