Submission #1177285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177285		AlgorithmWarrior	Jousting tournament (IOI12_tournament)	C++20	100 / 100	34 ms	2376 KiB

tournament

#include <bits/stdc++.h>

using namespace std;

const int MAX=1e5+5;
const int LOG=20;

int ub(int x){
    return x&(-x);
}

struct AIB{
    int n;
    int v[MAX];
    void add(int pos,int val){
        while(pos<=n){
            v[pos]+=val;
            pos+=ub(pos);
        }
    }
    int sum(int pos){
        int s=0;
        while(pos){
            s+=v[pos];
            pos-=ub(pos);
        }
        return s;
    }
    int bin_search(int sum){
        int poz=0,s=0;
        int i;
        for(i=LOG-1;i>=0;--i)
            if(poz+(1<<i)<=n && s+v[poz+(1<<i)]<sum){
                poz+=(1<<i);
                s+=v[poz];
            }
        return poz+1;
    }
}aibSet,aibSum;

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
    aibSet.n=N;
    aibSum.n=N;
    int i,j;
    for(i=1;i<=N;++i)
        aibSet.add(i,1);
    vector<int>ult(N-1);
    if(K[0]<R)
        ult[0]=0;
    else
        ult[0]=1;
    for(i=1;i<N-1;++i)
        if(K[i]<R)
            ult[i]=ult[i-1];
        else
            ult[i]=i+1;
    for(i=0;i<C;++i){
        ++S[i];
        ++E[i];
        for(j=S[i]+1;j<=E[i];++j){
            int pos=aibSet.bin_search(S[i]+1);
            aibSet.add(pos,-1);
        }
        int pos1=aibSet.bin_search(S[i]);
        int pos2=aibSet.bin_search(S[i]+1);
        if(ult[pos2-3]<=pos1-1){
            aibSum.add(pos1,1);
            aibSum.add(pos2,-1);
        }
    }
    int poz=0,best=-1;
    for(i=0;i<N;++i){
        int val=aibSum.sum(i+1);
        if(val>best){
            poz=i;
            best=val;
        }
    }
    return poz;
}

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