Submission #881792

#	Time	Username	Problem	Language	Result	Execution time	Memory
881792		NK_	Meetings (JOI19_meetings)	C++17	100 / 100	506 ms	1660 KiB

meetings

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
#include "meetings.h"

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

template<class T> using V = vector<T>;
using vi = V<int>;

const int nax = 2005;
vi can[nax];

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int piv;
int cmp(int x, int y) {
	// x < y
	return Query(piv, x, y) == x;
}

void solve(vi A) {
	if (sz(A) <= 1) return;

	shuffle(begin(A), end(A), rng);

	int u = A[0], v = A[1];

	for(auto x : A) can[x] = {};

	vi P;
	can[u].pb(u); can[v].pb(v);
	for(auto x : A) {
		if (x == u || x == v) continue;
		int r = Query(x, u, v);
		if (r == x) P.pb(r);
		can[r].pb(x);
	}

	piv = u;
	stable_sort(begin(P), end(P), cmp);
	P.insert(begin(P), u); P.pb(v);

	for(int i = 1; i < sz(P); i++) Bridge(min(P[i], P[i-1]), max(P[i], P[i-1]));

	for(auto i : P) solve(can[i]);
}

void Solve(int N) {
	vi A(N); iota(begin(A), end(A), 0);
	solve(A);
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 71 / 71