[Solution] Ants on a Stick Solution Round C 2022 - Kick Start 2022

[Solution] Ants on a Stick Solution Round C 2022 - Kick Start 2022

Problem

Ada has N$N$ ants labelled from 1$1$ to N$N$. She decides to test John's concentration skills. She takes a stick L$L$ cm long, and drops the ants on it.

The positions on the stick at which the ants are dropped are represented by an integer array P$P$, where ant i$i$ is dropped at the position Pi${\mathbf{P}}_{\mathbf{i}}$ (that is, Pi${\mathbf{P}}_{\mathbf{i}}$ cm away from the left end) on the stick. Each ant travels either to the left or right with a constant speed of 1$1$ cm per second. The initial directions of the ants is represented by an array D$D$, where the direction of ant i$i$ is Di${\mathbf{D}}_{\mathbf{i}}$: 0$0$ if left, and 1$1$ if right. When two ants meet, they bounce off each other and reverse their directions. The ants fall off the stick when they reach either end of it.

Ada challenges John to find the exact order in which the ants fall off the stick. John needs your help!

Input

The first line of the input gives the number of test cases, T$T$. T$T$ test cases follow.

Solution Click Below:-  CLICK HERE

The first line of each test case contains two integers, N$N$ and L$L$: the number of ants, and the length of the stick, respectively.
The next N$N$ lines describe the positions and directions of the ants. The i$i$-th line contains two integers, Pi${\mathbf{P}}_{\mathbf{i}}$ and Di${\mathbf{D}}_{\mathbf{i}}$: the position and direction of ant i$i$, respectively.

Output

For each test case, output one line containing Case #x$x$: A1A2…AN$A_1{A}_2\dots A_N$, where x$x$ is the test case number (starting from 1), and Ai$A_i$ is the label of the i$i$-th ant that falls off the stick. In other words, the first ant to fall off the stick is the ant labelled A1$A_1$, the second is the ant labelled A2$A_2$, and so on. 

New Password Solution Round C 2022

Range Partition Solution Round C 2022

Ants on a Stick Solution Round C 2022

Palindromic Deletions Solution Round C 2022

If multiple ants fall off at the same time, output their labels in the increasing order.

Limits

Memory limit: 1 GB.
1≤T≤100$1\le \mathbf{T}\le 100$.
N<L$\mathbf{N}<\mathbf{L}$.
Di∈{0,1}${\mathbf{D}}_{\mathbf{i}}\in \{0,1\}$, for all i$i$.
0<Pi<L$0<{\mathbf{P}}_{\mathbf{i}}<\mathbf{L}$, for all i$i$.
All Pi${\mathbf{P}}_{\mathbf{i}}$ are distinct.

Test Set 1

Time limit: 20 seconds.
1≤N≤10$1\le \mathbf{N}\le 10$.
1≤L≤100$1\le \mathbf{L}\le 100$.

Test Set 2

Time limit: 40 seconds.
1≤N≤103$1\le \mathbf{N}\le {10}^3$.
1≤L≤109$1\le \mathbf{L}\le {10}^9$.

Test Set 3

Time limit: 40 seconds.
1≤L≤109$1\le \mathbf{L}\le {10}^9$.
For at most 15 cases:
1≤N≤105$1\le \mathbf{N}\le {10}^5$.
For the remaining cases:
1≤N≤103$1\le \mathbf{N}\le {10}^3$.