Beta Round #66-B: Need For Brake

keyword

実装　C++

問題概要

N(<10^5)チームのチーム名とこれまでの得点が与えられる。最終ラウンドでは、上位M位までに対してP[i](>=0)点が与えられる。最終ラウンド終了時に、あるチームが取りうる順位の上限と下限を求める問題。同じ得点のときはチーム名の辞書順比較が入る。

解法

setとか使って書くだけ。M位以下の人には0点が与えられると考えたら少し楽になるかも。set >とかに対してメンバ関数lower_bound(x)がどう動くのか把握できた(S = {5,4,2,1}に対してS.lower_bound(3)の指す値は2。要するに挿入するならそこ、というiteratorが返される)。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
using namespace std;

char buf[30];
string myName;
int N, M;
vector<int> bbs;
vector< pair<int, string> > ts;

int high_solve(){
	set< pair<int, string> > tmp;
	vector<int> bs = bbs;
	set< pair<int, string> > result;
	pair<int, string> ttt;
	for(int i=0; i<N; i++){
		if(ts[i].second != myName){
			tmp.insert(ts[i]);
		}
		else{
			ttt = ts[i];
		}
	}
	sort(bs.rbegin(), bs.rend());
	result.insert( make_pair(ttt.first + bs.back(), ttt.second));
	ttt = *result.begin();
	bs.pop_back();

	while(!bs.empty() && !tmp.empty()){
		pair<int, string> top = *tmp.begin();
		if(top < ttt){
			top.first += bs.back(); bs.pop_back();
			result.insert(top);
			tmp.erase(tmp.begin());
		}
		else{
			break;
		}
	}

	while(!bs.empty() && !tmp.empty()){
		pair<int, string> a = ttt;
		a.first -= bs.back();
		set< pair<int,string> >::iterator itr = tmp.lower_bound(a);
		if(itr == tmp.end()){
			itr = tmp.begin();
		}
		pair<int, string> b = *itr;
		b.first += bs.back();
		bs.pop_back();
		result.insert(b);
		tmp.erase(itr);
	}

	for(typeof(tmp.begin()) itr = tmp.begin(); itr != tmp.end(); itr++){
		result.insert(*itr);
	}

	int a = 1;
	for(typeof(result.begin()) itr = result.begin(); itr != result.end(); itr++){
		if(itr->second == myName){
			return a;
		}
		else a++;
	}
	return -1;
}

int low_solve(){
	set< pair<int, string>, greater<pair<int,string> > >tmp;
	vector<int> bs = bbs;
	set< pair<int, string>, greater<pair<int,string> > > result;
	pair<int, string> ttt;
	for(int i=0; i<N; i++){
		if(ts[i].second != myName){
			tmp.insert(ts[i]);
		}
		else{
			ttt = ts[i];
		}
	}
	sort(bs.begin(), bs.end());
	result.insert( make_pair(ttt.first + bs.back(), ttt.second));
	ttt = *result.begin();
	bs.pop_back();


	while(!bs.empty() && !tmp.empty()){
		pair<int, string> a = ttt;
		a.first -= bs.back();
		typeof(tmp.begin()) itr = tmp.lower_bound(a);
		if(itr == tmp.end()){
			itr = tmp.begin();
		}
		pair<int, string> b = *itr;
		b.first += bs.back();
		bs.pop_back();
		result.insert(b);
		tmp.erase(itr);
	}

	for(typeof(tmp.begin()) itr = tmp.begin(); itr != tmp.end(); itr++){
		result.insert(*itr);
	}

	int a = 1;
	for(typeof(result.rbegin()) itr = result.rbegin(); itr != result.rend(); itr++){
		if(itr->second == myName){
			return a;
		}
		else a++;
	}
	return -1;
}

int main(){
	scanf("%d ",&N);
	for(int i=0; i<N; i++){
		int x;
		scanf("%s %d ", buf, &x);
		ts.push_back( make_pair(-x, string(buf)));
	}
	scanf("%d ", &M);
	for(int i=0; i<M; i++){
		int x;
		scanf("%d ",&x);
		bbs.push_back(-x);
	}
	while(bbs.size() < ts.size()){
		bbs.push_back(0);
	}
	scanf("%s ",buf);
	myName = string(buf);
	printf("%d ", high_solve());
	printf("%d\n", low_solve());
	return 0;
}