제출 #577921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
577921		Justin1	마상시합 토너먼트 (IOI12_tournament)	C++14	17 / 100	1087 ms	7344 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
 
struct qry{
	int l, r, id;
};

int root;
vector<int> ch[200005];
int par[200005];
int ar[200005], order[200005], sz[200005], pos[200005];
qry range[200005];

void maketree(int N, int C, int *S, int *E) {
	for (int i = 0; i < N; i++) range[i] = {i,i,i};
	for (int i = 0; i < C; i++) {
		range[S[i]].r = range[E[i]].r;
		for (int j = S[i]; j <= E[i]; j++) {
			ch[N+i].push_back(range[j].id);
			par[range[j].id] = N+i;
		}
		range[S[i]].id = root = N+i;
		for (int j = E[i]+1; j < N; j++) range[j-(E[i]-S[i])] = range[j];
		E[i] = range[S[i]].r, S[i] = range[S[i]].l;
	}
	par[root] = root;
}

void dfs(int id) {
	static int T = 0;
	pos[id] = T;
	order[T++] = id;
	sz[id] = 1;
	for (auto i : ch[id]) {
		dfs(i);
		sz[id] += sz[i];
	}
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	maketree(N,C,S,E); //try to make this less than O(N^2)
	dfs(root);
	int mx = -1, ans = -1;
	for (int i = 1; i < N; i++) ar[i] = (K[i-1] > R ? 1 : 0);
	for (int i = 0; i < N; i++) { //exhaust O(N)
		int wins = 0, cur = i, doneroot = 0;
		while (!doneroot) { //optimize using binary lifting O(log N)
			bool ok = 1;
			for (int j = pos[cur]; j < pos[cur]+sz[cur]; j++) {
				if (ar[order[j]]) ok = 0; //optimize using segment tree O(log N)
			}
			wins += ok;
			if (cur == root) doneroot = 1;
			cur = par[cur];
		}
		if (wins > mx) {
			mx = wins;
			ans = i;
		}
		swap(ar[i],ar[i+1]);
	}
	return ans;
}

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