JOI春合宿 2011-day4 IOI

問題文 : 国際情報オリンピック

解法 :

まず,

"G を，N 問の合計点が G 点以上の選手の人数が全体の 1 / 12 以上となるような最大の値とする．このとき，金メダルが与えられる条件は，N 問の合計点が G 点以上であることである．"

ということを, 問題を解きやすくするために言い換える. これは,

"最終日での順位が [全体の人数 / 12] の小数点を切り上げた順位よりも高い"

といいかえられる.

そこで, ある人の最終日での順位の最大値と最小値を考えれば良い. これは, 予め, 全員の最大得点と最小得点を考えてソートしておくと, 二分探索で効率良く求めることが出来る.計算量はO(k log k)である.

コード :

#include <cstdio>
#include <algorithm>

#define MAX_K (100000)

using namespace std;

int scoreMin[MAX_K], scoreMax[MAX_K];
int datMin[MAX_K], datMax[MAX_K];
int state[MAX_K];

int main()
{
	int k, n, m;
	
	scanf("%d %d %d", &k, &n, &m);
	
	for (int i = 0; i < k; i++){
		scanf("%d", scoreMin + i);
		scoreMax[i] = scoreMin[i] + (n - m) * 100;
		datMin[i] = scoreMin[i]; datMax[i] = scoreMax[i];
	}
	
	sort(datMin, datMin + k);
	sort(datMax, datMax + k);
	
	for (int i = 0; i < k; i++){
		int rankUp = k + 1 - (upper_bound(datMin, datMin + k, scoreMax[i]) - datMin);
		int rankDown = k + (n == m) - (upper_bound(datMax, datMax + k, scoreMin[i]) - datMax);
		state[i] = (rankUp <= (k + 11) / 12) + (rankDown <= (k + 11) / 12);
	}
	
	for (int i = 0; i < k; i++){
		if (state[i] > 1) printf("%d\n", i + 1);
	}
	
	printf("--------\n");
	
	for (int i = 0; i < k; i++){
		if (state[i]) printf("%d\n", i + 1);
	}
	
	return (0);
}