Submission #1153649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153649		enzy	Jousting tournament (IOI12_tournament)	C++20	49 / 100	1095 ms	8816 KiB

tournament

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int sp[maxn], marc[maxn], qtd, at[maxn];
vector<int>comeco[maxn], final[maxn];

int GetBestPosition(int n, int c, int r, int *k, int *s, int *e){
    set<pair<int,int>>caras;
    for(int i=0;i<n;i++){
        caras.insert({i,i});
        comeco[i].clear(); final[i].clear();
        sp[i]=at[i]=marc[i]=0;
    }
    vector<pair<int,pair<int,int>>>process;
    for(int i=0;i<c;i++){
        int l=s[i], r=e[i];
        int cnt=0;
        vector<pair<int,int>>aux;
        for(auto p : caras){
            if(l<=cnt) aux.push_back(p);
            cnt++;
            if(cnt>r) break;
        }
        int idl=aux[0].first, idr=aux.back().second;
        for(auto p : aux) caras.erase(p);
        caras.insert({idl,idr});
        process.push_back({i,{idl,idr}});
        comeco[idl].push_back(i); final[idr].push_back(i);
        //cout << idl << " " << idr << endl;
    }
    // começo supondo q o meu cara começa na pos 0
    for(int i=1;i<n;i++){
        sp[i]=sp[i-1];
        if(k[i-1]>r) sp[i]++;
    }
    //for(int i=0;i<n;i++) cout << sp[i] << " ";
    //cout << endl;
    for(auto p : process){
        int l=p.second.first, r=p.second.second, id=p.first;
        if(l==0) marc[id]=sp[r];
        else marc[id]=sp[r]-sp[l-1];
        //cout << id << " " << marc[id] << endl;
    }
    int resp=0, best=0; qtd=0;
    for(int i=0;i<n-1;i++){ // vou andando na pos q eu to brutando o meu cara
        for(int a : comeco[i]){
            at[a]++;
            if(!marc[a]) qtd++;
        }
        if(qtd>best){
            best=qtd;
            resp=i;
        }
        if(i==n-1) break;
        if(k[i]>r){ // esse cara vai da pos i+1, para a i
            for(int a : comeco[i+1]){
                marc[a]--;
                if(marc[a]==0&&at[a]) qtd++;
            }
            for(int a : final[i]){
                if(!marc[a]) qtd--;
                marc[a]++;
            }
        }
        for(int a : final[i]){
            at[a]--;
            if(!marc[a]) qtd--;
        }
    }
    return resp;
}

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