Submission #619106

#	Time	Username	Problem	Language	Result	Execution time	Memory
619106		errorgorn	Meetings (JOI19_meetings)	C++17	100 / 100	643 ms	1032 KiB

meetings

#include "meetings.h"

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

#define int long long
#define ii pair<int,int>
#define fi first
#define se second

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

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

int n;

void dnc(int l,int r,vector<int> line,vector<int> &res){
	if (line.empty()) return;
	
	int x=line[rng()%sz(line)];
	vector<int> vl,vr;
	for (auto it:line) if (it!=x){
		if (Query(l,x,it)==x) vr.pub(it);
		else vl.pub(it);
	}
	
	dnc(l,x,vl,res);
	res.pub(x);
	dnc(x,r,vr,res);
}

void solve(vector<int> idx){
	if (sz(idx)==1) return;
	if (sz(idx)==2){
		if (idx[0]>idx[1]) swap(idx[0],idx[1]);
		Bridge(idx[0],idx[1]);
		return;
	}
	
	int u,v;
	do{
		u=idx[rng()%sz(idx)];
		v=idx[rng()%sz(idx)];
	} while (u==v);
	
	map<int,vector<int> > m;
	m[u]={u},m[v]={v};
	for (auto it:idx) if (it!=u && it!=v){
		m[Query(u,v,it)].pub(it);
	}
	
	vector<int> line;
	for (auto [a,b]:m) if (a!=u && a!=v) line.pub(a);
	
	vector<int> res={u};
	dnc(u,v,line,res);
	res.pub(v);
	
	rep(x,0,sz(res)-1){
		if (res[x]<res[x+1]) Bridge(res[x],res[x+1]);
		else Bridge(res[x+1],res[x]);
	}
	
	for (auto [a,b]:m) solve(b);
}

void Solve(signed N) {
	n=N;
	
	vector<int> idx;
	rep(x,0,n) idx.pub(x);
	
	solve(idx);
}

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