pat1025 PAT Ranking
2034 단어 pat
사고방식: 시험장에서 한 번 정렬하고 마지막에 전체적으로 한 번 정렬한다.
코드
#include
#include
#include
#include
#include
using namespace std;
const int MAX_N = 100000;
struct Data {
string id;
int room;
int grade;
int local_rank;
int final_rank;
bool operator < (const Data& d) const {
return grade > d.grade || (grade == d.grade && id < d.id);
}
}data[MAX_N];
int len;
int N, K;
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
cin >> N; len = 0;
int p = 0;
for (int i = 1; i <= N; i++) {
scanf("%d", &K);
for (int j = 0; j < K; j++) {
cin >> data[len].id >> data[len].grade;
data[len].room = i;
len++;
}
sort(data+p, data+len);
int r = 0, cnt = 1, gr = -1;
for (int j = p; j < len; j++) {
if (data[j].grade == gr) {
cnt++; data[j].local_rank = r;
} else {
r += cnt;
cnt = 1;
data[j].local_rank = r;
gr = data[j].grade;
}
}
p = len;
}
sort(data, data+len);
int r = 0, cnt = 1, gr = -1;
for (int j = 0; j < len; j++) {
if (data[j].grade == gr) {
cnt++; data[j].final_rank = r;
} else {
r += cnt;
cnt = 1;
data[j].final_rank = r;
gr = data[j].grade;
}
}
cout << len << endl;
for (int i = 0; i < len; i++) {
cout << data[i].id << " " << data[i].final_rank << " " << data[i].room << " " << data[i].local_rank << endl;
}
return 0;
}