Submission #120966

#	Time	Username	Problem	Language	Result	Execution time	Memory
120966		KieranHorgan	Jousting tournament (IOI12_tournament)	C++17	49 / 100	1073 ms	12368 KiB

tournament

// #include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<pair<pair<long double,long double>, int>, null_type, less<pair<pair<long double,long double>, int>>, rb_tree_tag, 
             tree_order_statistics_node_update> ordered_set;

vector<int> AdjList[200005];
int sz[200005];
int curNode = 1;
int N, C, R, *K, *S, *E;
int actualIdxToNode[100005];
int nodeToActualIdx[200005];

int idxToAdd, sizeToAdd, curIdx;
ordered_set st;
void addNode() {
	if(st.empty()) st.insert({{0,1},1});
	auto it = st.find_by_order(idxToAdd);
	auto l = it->first.first;
	auto r = it->first.second;
	auto id = it->second;
	st.erase(it);
	long double x = (r-l)/sizeToAdd;
	for(int i = 0; i < sizeToAdd; i++) {
		AdjList[id].push_back(++curNode);
		st.insert({{l, l+x}, curNode});
		l += x;
	}
}

int curActualIdx = 0;
int depth[200005];
int kthAncestor[20][200005];
void getDepth(int u, int d) {
	depth[u] = d;
	if(AdjList[u].empty()) {
		sz[u] = 1;
		actualIdxToNode[curActualIdx] = u;
		nodeToActualIdx[u] = curActualIdx++;
		return;
	}
	for(auto v: AdjList[u]) {
		sz[u] += sz[v];
		kthAncestor[0][v] = u;
		getDepth(v, d-1);
	}
}

void calcKthAncestor() {
	kthAncestor[0][1] = 0;
	for(int i = 1+1; i <= curNode; i++)
		for(int j = 1; j < 20; j++) {
			kthAncestor[j][i] = kthAncestor[j-1][kthAncestor[j-1][i]];
			if(kthAncestor[j][i]==0) break;
		}
}

int lca(int a, int b) {
	if(depth[a] < depth[b])
		for(int j = 31-__builtin_clz(C-depth[a]); j >= 0; j--)
			if(depth[a] + (1<<j) <= depth[b])
				a = kthAncestor[j][a];
	if(depth[b] < depth[a])
		for(int j = 31-__builtin_clz(C-depth[b]); j >= 0; j--)
			if(depth[b] + (1<<j) <= depth[a])
				b = kthAncestor[j][b];
	for(int j = 31-__builtin_clz(C-depth[a]); j >= 0; j--)
		if(kthAncestor[j][a] != kthAncestor[j][b]) {
			a = kthAncestor[j][a];
			b = kthAncestor[j][b];
		}
	if(a != b) {
		a = kthAncestor[0][a];
		b = kthAncestor[0][b];
	}
	return a;
}

int closestToLeft[100005];
int closestToRight[100005];

int GetBestPosition(int N_, int C_, int R_, int *K_, int *S_, int *E_) {
	N=N_, C=C_, R=R_;
	K=K_, S=S_, E=E_;
	sz[1] = 1;
	ordered_set stt;
	for(int i = C-1; i >= 0; i--) {
		curIdx = 0;
		idxToAdd = S[i];
		sizeToAdd = E[i]-S[i]+1;
		addNode();
		if(i%30==0) {
			stt.clear();
			long double l = 0;
			long double x = (long double)1/(st.size());
			for(auto p: st) {
				p.first.first = l;
				p.first.second = l+x;
				l += x;
				stt.insert(p);
			}
			swap(st, stt);
		}
	}

	getDepth(1,C);
	calcKthAncestor();

	closestToLeft[0] = -1;
	for(int i = 1; i <= N; i++) {
		closestToLeft[i] = closestToLeft[i-1];
		if(K[i-1] > R)
			closestToLeft[i] = i-1;
	}

	closestToRight[N-1] = -1;
	for(int i = N-1-1; i >= 0; i--) {
		closestToRight[i] = closestToRight[i+1];
		if(K[i+1-1] > R)
			closestToRight[i] = i+1;
	}


	int ans = -1;
	int pos = -1;
	for(int i = 0; i < N; i++) {
		int a = 0;
		if(closestToLeft[i] == -1) {
			a = C-depth[actualIdxToNode[i]];
		} else {
			a = depth[lca(actualIdxToNode[i], actualIdxToNode[closestToLeft[i]])]-depth[actualIdxToNode[i]]-1;
		}
		int b = 0;
		if(closestToRight[i] == -1) {
			b = C-depth[actualIdxToNode[i]];
		} else {
			b = depth[lca(actualIdxToNode[i], actualIdxToNode[closestToRight[i]])]-depth[actualIdxToNode[i]]-1;
		}

		if(min(a,b) > ans) {
			ans = min(a,b);
			pos = i;
		}
	}

	return pos;
}

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 0 / 51