Submission #1159315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159315		OI_Account	Park (JOI17_park)	C++20	10 / 100	234 ms	680 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;
}

void solveTree(vector<int> vec) {
	/*cout << "hi " << ": ";
	for (auto x: vec)
		cout << x << ' ';
	cout << endl;*/
	if (vec.size() <= 2) {
		if (vec.size() == 2)
			write(vec[0], vec[1]);
		return;
	}
	int idx1 = rng() % (int) vec.size();
	int idx2 = rng() % ((int) vec.size() - 1);
	if (idx2 >= idx1)
		idx2++;
	int u = vec[idx1], v = vec[idx2];
	vector<int> vecU = {u}, vecV = {v}, vecMid;
	shuffle(vec.begin(), vec.end(), rng);
	for (auto x: vec)
		if (x != u && x != v) {
			if (isMiddle(x, u, v))
				vecU.push_back(x);
			else if (isMiddle(x, v, u))
				vecV.push_back(x);
			else
				vecMid.push_back(x);
		}
	if (vecMid.empty())
		write(u, v);
	else {
		shuffle(vecMid.begin(), vecMid.end(), rng);
		bool findU = false, findV = true;
		for (auto x: vecMid) {
			if (!findU && isAdj(x, u)) {
				write(x, u);
				findU = true;
			}
			if (!findV && isAdj(x, v)) {
				write(x, v);
				findV = true;
			}
		}
	}
	solveTree(vecU);
	solveTree(vecV);
	solveTree(vecMid);
}

void solveSubTree() {
	vector<int> vec;
	for (int i = 0; i < n; i++)
		vec.push_back(i);
	solveTree(vec);
}

void Detect(int T, int N) {
	n = N;
	if (T == 1)
		solveSub1();
	else if (T != 5)
		solveSubTree();
}

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