제출 #429626

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
429626		8e7	Park (JOI17_park)	C++14	10 / 100	1260 ms	540 KiB

park

#include "park.h"
//Challenge: Accepted
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <random>
#include <time.h>
#include <assert.h>
#include <unordered_map>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
//using namespace __gnu_pbds;
void debug() {cout << endl;}
template <class T, class ...U> void debug(T a, U ... b) { cout << a << " "; debug(b...);}
template <class T> void pary(T l, T r) {
	while (l != r) {cout << *l << " ";l++;}
	cout << endl;
}
#define ll long long
#define ld long double
#define maxn 1405
#define mod 1000000007
#define pii pair<long long, long long>
#define ff first
#define ss second

static int que[maxn];
vector<pii> ed;
int qcnt = 0;
int query(int a, int b) {
	if (a > b) swap(a, b);
	if (a == b || (que[a] == 0) || (que[b] == 0)) return 0;
	//debug(a, b);
	qcnt++;
	return Ask(a, b, que);
}
void solve(vector<int> v) {
	if (v.size() < 2) return;
	if (v.size() == 2) {
		ed.push_back({v[0], v[1]});
		return;
	}
	random_shuffle(v.begin(), v.end());
	int cent = v[0];
	for (int i = 0;i < maxn;i++) que[i] = 0;
	for (int i:v) que[i] = 1;
	int num =2 * __lg(v.size());
	for (int i:v) {	
		que[i] = 0;
		int cnt = 0;
		for (int j = 0;j < num;j++) {
			int ix = rand() % v.size(), iy = rand() % v.size();
			if (v[ix] == i) ix = (ix + 1) % v.size();
			while (iy != ix && v[iy] != i) {
				iy = (iy + 1) % v.size();
			}
			cnt += query(v[ix], v[iy]);	
		}
		que[i] = 1;
		if (cnt >= num) {
			cent = i;
			break;
		}
	}	
	//debug(cent);
	for (int i:v) que[i] = 0;
	que[cent] = 1;
	vector<int> adj;
	for (int i:v) {
		if (i == cent) continue;
		que[i] = 1;
		if (query(i, cent)) {
			ed.push_back({i, cent}), adj.push_back(i);
		}
		que[i] = 0;
	}
	for (int i:adj) {
		vector<int> rec;
		rec.push_back(i);
		for (int j:v) que[j] = 1;
		que[i] = 0;
		for (int j:v) {
			if (j != cent && j != i && !query(j, cent)) rec.push_back(j);
		}	
		//pary(rec.begin(), rec.end());
		for (int j:rec) v.erase(find(v.begin(), v.end(), j));
		for (int j:v) que[j] = 0;
		solve(rec);
	}
}
void Detect(int T, int N) {
	srand(time(NULL));
	vector<int> ini;
	for (int i = 0;i < N;i++) ini.push_back(i);
	solve(ini);
	for (auto i:ed) {
		if (i.ff > i.ss) swap(i.ff, i.ss);
		Answer(i.ff, i.ss);
	}
}
/*

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

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