Submission #288100

#	Time	Username	Problem	Language	Result	Execution time	Memory
288100		emanIaicepsa	Jousting tournament (IOI12_tournament)	C++14	17 / 100	983 ms	2048 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], 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;
    }
     
    void add(int x,int val){
    	for(;x<=n;x+=x&-x) bit[x]+=val;
    }
     
    void init(){
    	mem(bit, 0);
    	for(int i=1;i<=n;i++) add(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]);
    		used |= (mxid == x);
    		for(int j=l[i]+1;j<=r[i];j++){
    			int id = kth(l[i]+1);
    			used |= (id == x);
    			if(arr[id] > arr[mxid]){
    				add(mxid, -1);
    				mxid = id;
    			}
    			else add(id, -1);
    		}
    		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: 0 / 32
• Subtask 3: 0 / 51