Third Running Time
National Olympiad — Municipal round
Submission name: runners.cpp
Problem summary
Runners 1…N start one second apart in numerical order. They finish one second apart in a given permutation, with no ties in arrival. Find all runners whose elapsed running time is the third smallest distinct elapsed time.
Input
N and the permutation of runner IDs in finish order.
Output
Count followed by those runner IDs in increasing order, separated by single spaces; print only 0 if there are fewer than three distinct elapsed times.
Constraints
2<N<100.
Worked example
An independently prepared example for this explanation.
Input
5 3 1 5 2 4
Output
1 2
Solution analysis
- For runner v arriving in position i, its elapsed time differs from i−v by a common constant.
- Collect and sort the distinct values i−v.
- Use the third distinct value, then scan runner IDs increasingly.
Why it works
Subtracting the same constant from every elapsed time preserves equality and ordering, so the rank of i−v is exactly the rank of the actual duration.
Watch out. Third time means third distinct time, not third finisher.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Subtracting the same constant from every elapsed time preserves equality and ordering, so
// the rank of i−v is exactly the rank of the actual duration.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>t(n+1),vals;
for(int i=1;i<=n;i++){
int v;
cin>>v;
t[v]=i-v;
vals.push_back(t[v]);
}
sort(vals.begin(),vals.end());
vals.erase(unique(vals.begin(),vals.end()),vals.end());
vector<int>ans;
if(vals.size()>=3){
for(int v=1;v<=n;v++){
if(t[v]==vals[2]){
ans.push_back(v);
}
}
}
cout<<ans.size();
for(int v:ans){
cout<<' '<<v;
}
cout<<'\n';
}