Submission #520963

#	Time	Username	Problem	Language	Result	Execution time	Memory
520963		koioi.org-koosaga	Park (JOI17_park)	C++17	67 / 100	333 ms	836 KiB

park

#include "park.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pi;
const int MAXN = 1500;

static int Place[1400];

vector<int> gph[MAXN];
vector<int> ord;

void dfs(int x){
	ord.push_back(x);
	for(auto &y : gph[x]) dfs(y);
}

void Detect(int T, int N) {
	vector<int> v = {};
	for(int i = 1; i < N; i++){
		auto init = [&](){
			memset(Place, 0, sizeof(Place));
			for(int i = 0; i < N; i++) Place[i] = 1;
		};
		int s = 0, e = sz(v);
		while(s != e){
			int m = (s + e) / 2;
			init();
			for(int i = m; i < sz(v); i++) Place[v[i]] = 0;
			if(Ask(0, i, Place) == 1) e = m;
			else s = m + 1;
		}
		v.insert(v.begin() + s, i);
	}
	for(int i = 0; i < sz(v); i++){
		auto init = [&](){
			memset(Place, 0, sizeof(Place));
			for(int i = 0; i < N; i++) Place[i] = 1;
		};
		ord.clear();
		dfs(0);
		int s = 0, e = sz(ord) - 1;
		while(s != e){
			int m = (s + e) / 2;
			init();
			for(int i = m + 1; i < sz(ord); i++) Place[ord[i]] = 0;
			if(Ask(0, v[i], Place) == 1) e = m;
			else s = m + 1;
		}
		gph[ord[s]].push_back(v[i]);
	}
	for(int i = 0; i < N; i++){
		for(auto &j : gph[i]) Answer(min(i, j), max(i, j));
		gph[i].clear();
	}
}

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