Elimination Order in a Circular Marathon
Autumn Tournament (2013)
Submission name: run.cpp
Problem summary
Runners start at distinct clockwise positions on a circular track. Each moves at a constant speed; a runner caught by the runner immediately behind is eliminated. Print eliminations chronologically, then the surviving runners in increasing starting-number order.
Source clarification. The official checker groups simultaneous events and accepts any ordering within the same time group. The solution uses exact rational ordering. Editorial: https://infos.infosbg.com/files/Contests/ETI/2013/B/analyses/run_analysis.pdf
Input
N L, then N lines position speed, in increasing position order.
Output
Each eliminated number on its own line; then Winner(s): followed by the sorted survivors. Simultaneous eliminations may be listed in any order.
Constraints
1≤N≤500000; L<5000000; integer0≤D1<…<DN<L; speeds0<S≤5, specified to hundredths.
Worked example
Original statement sample.
Input
6 150 0 1.75 30 0.8 60 0.5 70 1 120 0.1 140 0.9
Output
2 3 5 4 6 Winner(s): 1
Solution analysis
- Only adjacent surviving runners can cause the next elimination. Store their circular order in next[] and previous[], and put each faster-behind/slower-ahead pair into a minimum heap. For original positions d[a],d[b], the clockwise gap is(d[b]−d[a]+L)%L; their meeting time is gap/(speed[a]−speed[b]).
- Pop the earliest still-valid event. Remove its front runner b, reconnect a directly to next[b], and schedule only that newly adjacent pair. Heap events involving an eliminated runner or a no-longer-adjacent pair are stale and must be ignored. Every actual removal creates at most one new candidate.
- Store speeds as integer hundredths and compare meeting-time fractions by cross multiplication, avoiding rounding-induced ordering errors. In the sample the eliminations are2,3,5,4,6; runner1 remains. When every remaining speed is equal, no faster adjacent pair exists and all survivors win.
Why it works
Before the first future collision, surviving runners retain their clockwise order, so that collision must involve adjacent runners. The heap contains the meeting event of every adjacent faster pair, and its minimum valid entry is therefore the next elimination. Removing its victim changes only one successor relation; rescheduling that pair preserves the invariant. Stale events cannot represent current collisions and are safely discarded.
Watch out. Use a circular successor, including last→first. Ignore stale events. Parse0.8 as0.80. Equal speeds never catch each other. The common factor100 in physical meeting times can be omitted when ordering events.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<queue>
#include<string>
#include<vector>
using namespace std;
struct Event{
long long gap;
int difference;
int behind;
int ahead;
};
struct Later{
bool operator()(const Event&a,const Event&b)const{
long long left=a.gap*b.difference;
long long right=b.gap*a.difference;
if(left!=right){
return left>right;
}
return a.ahead>b.ahead;
}
};
int hundredths(string text){
size_t dot=text.find('.');
if(dot==string::npos){
return stoi(text)*100;
}
string fraction=text.substr(dot+1);
fraction.resize(2,'0');
return stoi(text.substr(0,dot))*100+stoi(fraction);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,length;
cin>>n>>length;
vector<int>position(n),speed(n),next(n),previous(n);
vector<bool>alive(n,true);
for(int i=0;i<n;i++){
string value;
cin>>position[i]>>value;
speed[i]=hundredths(value);
next[i]=(i+1)%n;
previous[i]=(i+n-1)%n;
}
priority_queue<Event,vector<Event>,Later>events;
auto schedule=[&](int a){
int b=next[a];
if(a!=b&&speed[a]>speed[b]){
long long gap=(position[b]-position[a]+length)%length;
events.push({gap,speed[a]-speed[b],a,b});
}
};
for(int i=0;i<n;i++){
schedule(i);
}
while(!events.empty()){
Event event=events.top();
events.pop();
int a=event.behind;
int b=event.ahead;
if(!alive[a]||!alive[b]||next[a]!=b){
continue;
}
cout<<b+1<<'\n';
alive[b]=false;
next[a]=next[b];
previous[next[b]]=a;
// Only the killer's new successor can create a new candidate event.
schedule(a);
}
cout<<"Winner(s):";
for(int i=0;i<n;i++){
if(alive[i]){
cout<<' '<<i+1;
}
}
cout<<'\n';
}