Submission #1159348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159348		OI_Account	Park (JOI17_park)	C++20	47 / 100	197 ms	660 KiB

park

#include "park.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 1400;
static int Place[1400];

int n;
bitset<N + 1> mark;

bool query(int u, int v) {
	if (u > v)
		swap(u, v);
	for (int i = 0; i < n; i++)
		Place[i] = mark[i];
	return Ask(u, v, Place);
}

void write(int u, int v) {
	//cout << u << ' ' << v << endl;
	if (u > v)
		swap(u, v);
	Answer(u, v);
}

bool isAdj(int u, int v) {
	mark.reset();
	mark[u] = mark[v] = 1;
	return query(u, v);
}

void solveSub1() {
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)	
			if (isAdj(i, j))
				write(i, j);
}

int cmpU, cmpV;

bool cmp(int u, int v) {
	mark.set();
	mark[v] = 0;
	return query(cmpU, u);
}

void solveSub2() {
	vector<int> vec;
	for (int i = 1; i < n - 1; i++)
		vec.push_back(i);
	cmpU = 0;
	cmpV = n - 1;
	sort(vec.begin(), vec.end(), cmp);
	if (vec.size()) {
		write(0, vec[0]);
		write(vec.back(), n - 1);
	}
	for (int i = 0; i + 1 < vec.size(); i++)
		write(vec[i], vec[i + 1]);
}

mt19937 rng(123);

bool isMiddle(int u, int w, int v) {
	mark.set();
	mark[w] = 0;
	return query(u, v) == false;
}

int h[N + 10], col[N + 10];
vector<int> vec[N + 10], adj[N + 10];

int sel(vector<int> vec, int u) {
	if (vec.size() == 1)
		return vec[0];
	int mid = (int) vec.size() / 2;
	vector<int> vecL, vecR;
	for (int i = 0; i < (int) vec.size(); i++)
		if (i < mid)
			vecL.push_back(vec[i]);
		else
			vecR.push_back(vec[i]);
	mark.set();
	for (auto x: vecL)
		mark[x] = 0;
	if (query(0, u))
		return sel(vecR, u);
	return sel(vecL, u);
}

void solveSub3() {
	h[0] = 1;
	col[0] = true;
	for (int hi = 2; hi <= 9; hi++) {
		for (int i = 0; i < n; i++)
			mark[i] = col[i];
		for (int  i = 0; i < n; i++)
			if (!col[i]) {
				mark[i] = 1;
				if (query(0, i)) {
					h[i] = hi;
					col[i] = true;
					vec[hi].push_back(i);
					//cout << i << " -> " << hi << endl;
				}
				mark[i] = 0;
			}
	}
	for (int i = 0; i < n; i++)
		if (!col[i]) {
			h[i] = 10;
			vec[10].push_back(i);
		}
	for (int hi = 2; hi <= 10; hi++)
		for (auto u: vec[hi]) {
			//cout << hi << ": " << u << endl;
			int pnt = 0;
			for (int tmp = 1; tmp != hi - 1; tmp++)
				pnt = sel(adj[pnt], u);
			//cout << pnt << endl;
			write(u, pnt);
			adj[pnt].push_back(u);
			//cout << hi << endl;
		}
}

void Detect(int T, int N) {
	n = N;
	if (T == 1)
		solveSub1();
	else if (T == 2)
		solveSub2();
	else if (T == 3)
		solveSub3();
}

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