Ranking
National Olympiad — Regional round (2023 season)
Submission name: ranking.cpp
Problem summary
For each contestant and each of K subtasks, take the greatest score from all of their submissions, using zero for a contestant with none. Rank by decreasing sum of these maxima, breaking ties by increasing name.
Input
N M K, N contestant names, then M submissions: name followed by K subtask scores.
Output
N lines in rank order: name, total score, and the K subtask maxima.
Constraints
2 ≤ N,M ≤ 250000; 1 ≤ K ≤ 5; 0 ≤ scores ≤ 10^9; names use at most 10 lowercase Latin letters.
Worked example
Official example, transcribed with whitespace restored from the PDF.
Input
5 6 2 benq tourist radewoosh maroonrk sorting sorting 40 10 tourist 50 50 maroonrk 20 30 sorting 20 150 tourist 150 0 radewoosh 25 25
Output
tourist 200 150 50 sorting 190 40 150 maroonrk 50 20 30 radewoosh 50 25 25 benq 0 0 0
Solution analysis
- Map each registered name to an array index. Initialize its K component scores to zero. When reading a submission, update each component independently with the maximum of the old score and the new score.
- After all submissions, compute each total as the sum of the component maxima, using a 64-bit integer. Sort contestant indices by descending total and, for equal totals, ascending name. Output both the total and its component scores.
- In the example, tourist combines 150 from one submission with 50 from another, producing 200. maroonrk and radewoosh both score 50, and alphabetical order puts maroonrk first.
Why it works
After processing any submission prefix, each stored component is exactly the largest observed score for that contestant and subtask, by induction on updates. Thus the final sums are the required scores. The sorting comparator implements exactly the two stated ranking keys, so the output is the required complete ranking.
Watch out. Take per-subtask maxima across submissions, not the best single submission. Totals can exceed 32-bit range.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: After processing any submission prefix, each stored component is exactly the largest
// observed score for that contestant and subtask, by induction on updates. Thus the final sums are the
// required scores.
#include<algorithm>
#include<array>
#include<iostream>
#include<numeric>
#include<string>
#include<unordered_map>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m,k;
cin>>n>>m>>k;
vector<string>names(n);
unordered_map<string,int>index;
index.reserve(2*n);
for(int i=0;i<n;++i){
cin>>names[i];
index[names[i]]=i;
}
vector<array<long long,5>>best(n);
for(int i=0;i<m;++i){
string name;
cin>>name;
int who=index.at(name);
for(int j=0;j<k;++j){
long long score;
cin>>score;
best[who][j]=max(best[who][j],score);
}
}
vector<long long>total(n);
vector<int>order(n);
iota(order.begin(),order.end(),0);
for(int i=0;i<n;++i){
for(int j=0;j<k;++j){
total[i]+=best[i][j];
}
}
sort(order.begin(),order.end(),[&](int a,int b){
if(total[a]!=total[b]){
return total[a]>total[b];
}
return names[a]<names[b];
});
for(int who:order){
cout<<names[who]<<' '<<total[who];
for(int j=0;j<k;++j){
cout<<' '<<best[who][j];
}
cout<<'\n';
}
}