第6回日本情報オリンピック 春合宿 1日目 問題1 「得点」 (Score)

priority_queueやsortを使い、大きいほうから順に並べてその得点の順位を決めます。

計算量はO(n log n)だけどこの問題はそこまで計算量気にしなくてよさそう。

#include <bits/stdc++.h>

using namespace std;

int d[100005];
int jun[120];

int main(){

	priority_queue<int> que;
	int n;
	scanf("%d",&n);
	for(int i = 0;i < n;i++){
		scanf("%d",&d[i]);
		que.push(d[i]);
	}
	int pre=101;
	for(int i = 1;i <= n;i++){
		int nau = que.top(); que.pop();
		if(pre > nau){
			jun[nau] = i;
			pre = nau;
		}
	}
	for(int i = 0;i < n;i++){
		printf("%d\n",jun[d[i]]);
	}
	return 0;
}