PAT 1025 PAT Ranking

7910 ワード

#include <cstdio>

#include <cstdlib>

#include <vector>

#include <cstring>

#include <queue>

#include <algorithm>



using namespace std;



class Man {

public:

    char id[14];

    int location;

    int score;

    int local_rank;

};



class RankCmp{

public:

    bool operator () (const Man* a, const Man* b) {

        if (a->score > b->score) {

            return true;

        } else if (a->score < b->score) {

            return false;

        }



        return strcmp(a->id, b->id) < 0;

    }

};



void do_local_rank(vector<Man*> &v) {

    int len = v.size();

    if (len < 1) return;

    

    int last_score = v[0]->score;

    v[0]->local_rank = 1;

    

    for (int i=1; i<len; i++) {

        Man& cur = *v[i];

        if (cur.score != last_score) {

            cur.local_rank = i + 1;

            last_score = cur.score;

        } else {

            cur.local_rank = v[i - 1]->local_rank;

        }

    }

}



void print(vector<Man*> &v) {

    int len = v.size();

    for (int i=0; i<len; i++) {

        printf("%s %d %d
", v[i]->id, v[i]->score, v[i]->local_rank); } } int main() { int N, K, total = 0; scanf("%d", &N); vector<vector<Man*> > locations(N); Man tmp; RankCmp rankcmp; for (int i=0; i<N; i++) { scanf("%d", &K); for (int j=0; j<K; j++) { total++; scanf("%s%d", tmp.id, &(tmp.score)); tmp.location = i + 1; locations[i].push_back(new Man(tmp)); } sort(locations[i].begin(), locations[i].end(), rankcmp); do_local_rank(locations[i]); } printf("%d
", total); vector<Man*> all; for (int i=0; i<N; i++) { all.insert(all.end(), locations[i].begin(), locations[i].end()); } sort(all.begin(), all.end(), rankcmp); int last_rank = 0, last_score = -1; for (int i=0; i<total; i++) { Man& cur = *all[i]; if (cur.score != last_score) { last_score = cur.score; last_rank = i + 1; } printf("%s %d %d %d
", cur.id, last_rank, cur.location, cur.local_rank); } return 0; }

最後のグローバルソート300*100 log(300*100)は、優先キューで300*100 log(100)に変更できる場合、昇格も大きくなく、低下する可能性があります.