Hints → https://atcoder.jp/contests/arc149/editorial/4961

[1] Observations

Let us compute the results for all initial positions \(1, 2, \ldots, 10^6\). We label the piece whose initial position is \(x\) with the ID \(x\).

Let us observe how these pieces move. Initially, the \(10^6\) pieces are arranged consecutively in the order of ID on the positive part of the number line. Here, the relationship between the IDs and coordinates of the pieces is simple, and we can easily handle the destinations of the move altogether.

The first move will divide the sequence of pieces into three parts: negative, origin, and positive. There is nothing to compute for a piece that comes to the origin, so let us consider the negative and positive parts. If we only look at one of these parts, the second move is represented by the same formula, so we might be able to handle the destinations of the second move altogether. Troublingly, however, the formulae for the two parts are different. Let us think of a way to deal with this.

[2] Solution

For two pieces that are at coordinates \(x\) and \(-x\) at some time, their subsequent movements will be symmetric with respect to the origin. Thus, for these pieces, we just need to compute the movement of only one of them.

Then, among the two sequences of pieces on the positive and negative parts of the line, we do not need to manage the shorter one, that is, compute the movements of the pieces that belong to it. Thus, one can solve the problem by implementing the following appropriately.

• Simulate the movement of the sequence of pieces whose coordinates have the same sign by maintaining the relationship between the IDs and coordinates of the pieces.
• When a piece arrives at the origin, fix the answer for that piece, and stop tracing that piece.
• When the sequence of pieces is divided into positive and negative parts, stop tracing the pieces belonging to the shorter part after recording the IDs of the pieces at the symmetric positions. For these pieces, find the answer after all moves using the recorded IDs.

Here, the number of times one fixes the answer for a piece or records the ID of the piece at the symmetric position is at most the total number of pieces, so it takes \(O(M + \max X_i)\) time.

To elaborate, when the pieces are divided into positive and negative parts, consider spanning a (directed) edge from each piece belonging to the shorter part to the symmetric piece. Then, the pieces form a directed forest. After all moves, one can propagate the answer from the roots to find the answers for all pieces. See also the following image.

Sample submission

https://atcoder.jp/contests/arc149/submissions/35220962