| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 서브태스크 참고 (추가 시간 없음) | 1024 MB | 38 | 21 | 14 | 56.000% |
Ada has $N$ ants labelled from 1ドル$ to $N$. She decides to test John's concentration skills. She takes a stick $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,ドル where ant $i$ is dropped at the position $P_i$ (that is, $P_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ドル$ cm per second. The initial directions of the ants is represented by an array $D,ドル where the direction of ant $i$ is $D_i$: 0ドル$ if left, and 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!
The first line of the input gives the number of test cases, $T$. $T$ test cases follow.
The first line of each test case contains two integers, $N$ and $L$: the number of ants, and the length of the stick, respectively.
The next $N$ lines describe the positions and directions of the ants. The $i$-th line contains two integers, $P_i$ and $D_i$: the position and direction of ant $i,ドル respectively.
For each test case, output one line containing Case #x: A1A2…AN, where $x$ is the test case number (starting from 1), and $A_i$ is the label of the $i$-th ant that falls off the stick. In other words, the first ant to fall off the stick is the ant labelled $A_1,ドル the second is the ant labelled $A_2,ドル and so on. If multiple ants fall off at the same time, output their labels in the increasing order.
시간 제한: 20 초
시간 제한: 40 초
시간 제한: 40 초
3 1 5 1 1 2 7 4 1 5 0 4 10 8 0 2 1 6 1 4 0
Case #1: 1 Case #2: 2 1 Case #3: 1 2 3 4
In Sample Case #1, as there is only a single ant (labelled 1ドル$), it is the only one to fall off. The time at which it falls off is 4ドル$ seconds.
In Sample Case #2, the two ants move towards each other, meet at 0ドル.5$ seconds and reverse their directions. Ant 2ドル$ then reaches the right end of the stick at 3ドル$ seconds, whereas ant 1ドル$ reaches the left end at 5ドル$ seconds. Thus, ant 2ドル$ falls off the stick, followed by ant 1ドル$.
In Sample Case #3, ants 2ドル$ and 4ドル$ move towards each other and meet at 1ドル$ second. Similarly, ants 1ドル$ and 3ドル$ also move towards each other and meet at 1ドル$ second. All 4ドル$ ants then change directions.
Contest > Google > Kick Start > Google Kick Start 2022 > Round C C번