Cows Around a Circular Street
National Olympiad — National round (2026, shared AB)
Submission name: madcows.cpp
Problem summary
Cows start at increasing coordinates P on a circle of length L and move at unit speed in directions D. Two cows meeting head-on immediately reverse directions. Return the position of cow C[j] at integer time T[j].
Input
Grader calls std::vector<int> solve(int L, std::vector<int> P, std::vector<int> D, std::vector<int> C, std::vector<int> T). Local grader: N L, positions, directions, Q, then C T pairs.
Output
Return the queried positions in [0,L), in the original order.
Constraints
2 ≤ N ≤ 1,000,000; 1 ≤ Q ≤ 1,000,000; N ≤ L ≤ 10^9; distinct increasing positions; D[i] ∈ {−1,1}; 0 ≤ C[j] < N; 0 ≤ T[j] ≤ 10^9.
Worked example
An independently prepared example for this explanation.
Input
3 6 0 2 5 -1 1 1 3 0 2 2 1 1 5
Output
1 5 4
Solution analysis
- Let ghost cows pass straight through each other and exchange name tags at every head-on meeting. A name tag follows exactly the bouncing trajectory of the corresponding real cow. Store the initial ghost positions in two sorted arrays, one for each direction. If all directions agree, answer directly.
- Consider a tag initially on a clockwise ghost at group index a. Its ghost sequence is clockwise[a], counterclockwise[b], clockwise[a−1], counterclockwise[b+1], clockwise[a−2], and so on, with cyclic indices; b is the first counterclockwise ghost clockwise from the starting position. For an initially counterclockwise tag, reverse all index directions. The first transfer takes half the directed initial distance between the first two ghosts.
- Each subsequent transfer takes half a gap between consecutive initial ghosts of the same direction. Thus, for s transfers, twice the elapsed time is the first directed distance plus the sum of floor(s/2) backward gaps in the starting group and floor((s−1)/2) forward gaps in the other group, with directions reversed for a counterclockwise start. A cyclic gap sum is computed in constant time: full turns times L plus a directed endpoint difference modulo L.
- Binary-search the greatest s with doubled time at most 2T. Initial positions are distinct integers, so the first distance and every same-direction gap are at least one; consequently s ≤ 2T. From the parity of s, identify the ghost now carrying the tag and return its original position plus its own direction times T, modulo L. In the first example, tag 0 transfers across the seam to the ghost initially at 5 after half a minute; following the alternating sequence gives position 1 at time 2.
Why it works
Passing ghosts with exchanged tags has the same positions and velocities for each tag as an instantaneous reversal. The next opposite-direction ghost encountered by a tag is the next one in cyclic order, so transfers alternate between the two arrays in the stated directions. At a transfer the previous two ghosts coincide; the distance to the next carrier is exactly the fixed gap between two same-direction ghosts. Relative speed two makes half that gap the next transfer duration. Summing these durations gives the doubled-time formula. It increases strictly, so binary search finds precisely the transfers completed by T. The selected ghost then has the correct position; at an exact collision both possible carriers share that position.
Watch out. Use doubled times to retain half-minute collisions exactly. A full turn in a singleton direction group costs L, not zero. Normalize negative remainders and use 64-bit products.
Commented C++17 solution
Grader function only; no main. The displayed example is the official local-grader format.
#include<vector>
#include<algorithm>
#include<cstdint>
std::vector<int>solve(
int L,std::vector<int>P,std::vector<int>D,std::vector<int>C,std::vector<int>T){
std::vector<int>positions[2];
int n=static_cast<int>(P.size());
std::vector<int>index(n);
for(int i=0;i<n;++i){
int group=D[i]==1?1:0;
index[i]=static_cast<int>(positions[group].size());
positions[group].push_back(P[i]);
}
auto modulo=[](long long value,long long modulus){
value%=modulus;
return value<0?value+modulus:value;
};
// Travel through k cyclic gaps in the selected index direction.
auto distance=[&](const std::vector<int>&a,int start,long long k,int step){
long long size=static_cast<long long>(a.size());
long long result=(k/size)*L;
int finish=static_cast<int>(modulo(start+step*(k%size),size));
long long remainder=step==1?a[finish]-a[start]:a[start]-a[finish];
return result+modulo(remainder,L);
};
std::vector<int>answer;
answer.reserve(C.size());
for(int j=0;j<static_cast<int>(C.size());++j){
int cow=C[j];
int direction=D[cow];
int group=direction==1?1:0;
const auto&own=positions[group];
const auto&other=positions[1-group];
if(other.empty()){
answer.push_back(static_cast<int>(modulo(P[cow]+1LL*direction*T[j],L)));
continue;
}
int a=index[cow];
int b;
if(direction==1){
b=static_cast<int>(std::upper_bound(other.begin(),other.end(),P[cow])-other.begin());
b%=static_cast<int>(other.size());
}
else{
b=static_cast<int>(std::lower_bound(other.begin(),other.end(),P[cow])-other.begin())-1;
if(b<0){
b+=static_cast<int>(other.size());
}
}
long long first=modulo(1LL*direction*(other[b]-P[cow]),L);
auto doubledTime=[&](long long swaps){
if(swaps==0){
return 0LL;
}
return first+distance(own,a,swaps/2,-direction)+
distance(other,b,(swaps-1)/2,direction);
};
long long low=0;
long long high=2LL*T[j]+1;
while(high-low>1){
long long middle=(low+high)/2;
if(doubledTime(middle)<=2LL*T[j]){
low=middle;
}
else{
high=middle;
}
}
int initial;
int ghostDirection;
if(low%2==0){
int at=static_cast<int>(modulo(a-1LL*direction*(low/2),own.size()));
initial=own[at];
ghostDirection=direction;
}
else{
int at=static_cast<int>(modulo(b+1LL*direction*(low/2),other.size()));
initial=other[at];
ghostDirection=-direction;
}
answer.push_back(static_cast<int>(modulo(initial+1LL*ghostDirection*T[j],L)));
}
return answer;
}