Codeforces Beta #66 B. 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 ); }