Timus-1100 : Final Standings

問題概要

(id, solved)の組み合わせがN(<1.5*10^5)個与えられる。これをsolvedをキーとして降順にソートせよ。ただしバブルソートと結果が同じにならなければならない。

解法

バブルソートと同じというのは、単純に安定ソートであれば良い。なのでstable_sortを用いれば良い。ちなみに、stable_sortの実装はマージソートだったような記憶がある(少しあやふや)。最悪、stable_sortとか知らなくても元のインデックスを第2キーにするだけでよい。

acceptされたコード

計算量O(N*logN)。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 150000;

struct team{
	int id, solved;
};

bool operator<(const team& lhs, const team& rhs){
	return lhs.solved > rhs.solved;
}

team ts[MAX_N];

int main(){
	int N;
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%d%d", &ts[i].id, &ts[i].solved);
	}

	stable_sort(ts, ts+N);

	for(int i=0; i<N; i++){
		printf("%d %d\n", ts[i].id, ts[i].solved);
	}

	return 0;
}