Rank Staggered-Start Runners
National Olympiad — Municipal round (2014 season)
Submission name: klassir.cpp
Problem summary
Runners 1,2,3,4 start one second apart in numerical order and arrive one second apart in the given order. Rank them by elapsed running time, breaking ties by smaller runner number.
Input
A permutation of 1,2,3,4 giving arrival order.
Output
Runner numbers in increasing elapsed-time order.
Constraints
Exactly four distinct runners numbered 1–4.
Worked example
Input and output for the worked example discussed below.
Input
1 2 4 3
Output
4 1 2 3
Solution analysis
- Choose the first departure time as zero. Runner id starts at id−1. Arrival times share an unknown common offset T, but the runner at arrival position p has arrival time T+p.
- Subtracting departure time gives T+p−(id−1). The common T does not affect rankings, so store the key p−(id−1). Sort pairs (key,id), which also applies the required numerical tie break.
- For arrival order 1,2,4,3, keys are 0,0,−1,1. Runner 4 has the smallest elapsed time, runners 1 and 2 tie and appear in that order, and runner 3 is last. Negative reduced keys are harmless because the omitted T is common.
Why it works
Subtracting each runner’s actual departure time from their arrival time gives the true elapsed time. Removing one common offset preserves every comparison and equality. Lexicographic pair sorting therefore ranks true times and resolves equal times by ID.
Watch out. Arrival order alone is not the result because departure times differ. Compare running durations, not finish times. Preserve the smaller-ID tie break.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<cmath>
#include<iostream>
#include<limits>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<vector>
using namespace std;
int main(){
vector<pair<int,int>>ranking;
for(int position=0;position<4;position++){
int id;
cin>>id;
// The common unknown first-arrival time cancels from comparisons.
ranking.push_back({position-(id-1),id});
}
sort(ranking.begin(),ranking.end());
for(int index=0;index<4;index++){
if(index>0){
cout<<' ';
}
cout<<ranking[index].second;
}
cout<<'\n';
}