Submission #288151

#	Time	Username	Problem	Language	Result	Execution time	Memory
288151		emanIaicepsa	Jousting tournament (IOI12_tournament)	C++14	49 / 100	983 ms	1408 KiB

tournament

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,fma,sse,sse2,sse3,avx2")
#include<bits/stdc++.h>
#define mem(x,i) memset(x,i,sizeof(x))
#define dbg(x) cerr<<#x<<" = "<<x<<'\n';
using namespace std;
int bit[5005], arr[5005], l[5005], r[5005], pre[5005], nxt[5005], n, lgn, c;
 
int kth(int k){
	int p = 0;
	for(int i=lgn;i>=0;i--){
		int np = p + (1<<i);
		if(np <= n && bit[np] < k){
			k -= bit[np];
			p = np;
		}
	}
	return p+1;
}
 
inline void sub(int x){
	for(;x<=n;x+=x&-x) bit[x]--;
}
 
void init(){
	mem(bit, 0);
	for(int i=1;i<=n;i++){
		bit[i]++;
		if(i+(i&-i)<=n)bit[i+(i&-i)] += bit[i];
		pre[i] = i - 1;
		nxt[i] = i + 1;
	}
}
 
int solve(int x){
	init();
	int ans = 0;
	for(int i=1;i<=c;i++){
		bool used = 0;
		int mxid = kth(l[i]), id = nxt[mxid];
		used |= (mxid == x);
		for(int j=0,len=r[i]-l[i];j<len;j++,id=nxt[mxid]){
			used |= (id == x);
			if(arr[id] > arr[mxid]){
				pre[id] = pre[mxid];
				nxt[pre[id]] = id;
				sub(mxid);
				mxid = id;
			}
			else{
				nxt[mxid] = nxt[id];
				pre[nxt[id]] = mxid;
				sub(id);
			}
		}
		if(mxid == x) ans++;
		else if(used) return ans;
	}
	return ans;
}
 
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	auto st = clock();
	n = N;
	c = C;
	lgn = __lg(n);
	arr[1] = R;
	for(int i=2;i<=n;i++) arr[i] = K[i-2];
	for(int i=1;i<=c;i++) l[i] = S[i-1]+1, r[i] = E[i-1]+1;
	int ans = 0, cur = solve(1);
	for(int i=1;i<n;i++){
		if((clock() - st) * 1.0 / CLOCKS_PER_SEC > 0.98) return ans;
		swap(arr[i], arr[i+1]);
		int x = solve(i+1);
		if(x > cur) ans = i, cur = x;
	}
	return ans;
}

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