Codeforces Beta #66 B. Need For Brake

Need For Brake

Vasyaが最高の順位を取る時、Vasyaは最高点。この状態で一度ソートして、Vasyaより順位が下のレーサーに対し、低い点数を順に割り当てていく。ただし、最も低い点を割り当ててもVasyaより高順位になるレーサーは除く。
Vasyaが最低の順位を取る時、Vasyaは最低点。この状態で一度ソートして、Vasyaより順位が下のレーサーに対し、そのレーサーがVasyaを超える最小の点数を割り当てていく。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

struct R
{
    string n;
    int a;
    bool operator<(const struct R& r) { return a>r.a || a==r.a && n<r.n; }
};

int main()
{
    int n; cin>>n;
    vector<R> r(n);
    for ( int i=0; i<n; i++ )
        cin >> r[i].n >> r[i].a;
    int m; cin>>m;
    vector<int> b(n);
    for ( int i=0; i<m; i++ )
        cin >> b[i];
    sort(b.begin(),b.end());
    string name; cin>>name;

    vector<R> rt = r;
    
    //  最高順位
    for ( int i=0; i<n; i++ )
        if ( r[i].n == name )
            r[i].a += b[n-1];   //  Vasyaは最高点
    sort(r.begin(),r.end());

    int p = 0;      //  Vasyaの位置
    for ( int i=0; i<n; i++ )
        if ( r[i].n == name )
            p = i;
    
    int high = p+1;
    int bp = 0;
    for ( int i=p+1; i<n; i++ )
    {
        //  残っている最小の点数でもVasyaより上の順位になるなら
        //  このレーサーの順位はVasyaより上
        r[i].a += b[bp];
        if ( r[i] < r[p] )
            high++;
        else
            bp++;
    }

    //  最低順位
    r = rt;

    for ( int i=0; i<n; i++ )
        if ( r[i].n == name )
            r[i].a += b[0]; //  Vasyaは最低点
    sort(r.begin(),r.end());

    p = 0;      //  Vasyaの位置
    for ( int i=0; i<n; i++ )
        if ( r[i].n == name )
            p = i;
    
    int low = p+1;
    bp = 1;
    for ( int i=p+1; i<n; i++ )
    {
        //  Vasyaより上の順位となる、なるべく低い点数を割り当てる
        for ( ; bp<n; bp++ )
        {
            R t = r[i];
            t.a += b[bp];
            if ( t < r[p] )
                break;
        }

        if ( bp < n )
            low++,
            bp++;
    }

    printf( "%d %d\n", high, low );
}