아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

순환 마라톤

시간 제한3초메모리 제한256 MB

요약
원형 트랙 위 주자들이 앞선 주자를 따라잡아 탈락시키며 탈락 순서와 최종 생존자를 출력합니다.
난이도

보통10점 중 7점

유형
힙, 연결 리스트, 시뮬레이션, 수학
정답자
아직 제출이 없습니다

문제

순환 마라톤은 길이 LL인 원형 트랙 위에서 진행된다. 출발/결승 지점을 하나 정하고, NN명의 주자가 시계 방향으로 출발 지점에서부터 거리 DiD_i만큼 떨어진 위치에 서며, 출발 지점에 가장 가까운 주자부터 11번부터 NN번까지 출발 번호를 받는다.

출발 신호 후 각 주자는 자신의 속도 SiS_i로 시계 방향으로 달린다. 앞에 있는 주자를 따라잡으면 따라잡힌 주자는 탈락한다.

더 이상 탈락이 일어나지 않을 때까지 경기를 진행한 뒤, 트랙에 남아 있는 주자를 우승자로 발표한다. 탈락 순서를 출력하는 프로그램을 작성하시오.

입력

첫 줄에 양의 정수 NN, LL (N≤500 000N \leq 500\,000, L<5 000 000L < 5\,000\,000)이 주어진다.

다음 NN줄의 ii번째 줄에는 ii번 주자의 출발 위치 DiD_i와 속도 SiS_i가 주어진다. 0≤D1<D2<⋯<DN<L0 \leq D_1 < D_2 < \cdots < D_N < L이고, SiS_i는 소수점 둘째 자리까지의 실수이며 0<Si≤50 < S_i \leq 5이다. 거리는 미터, 속도는 초당 미터 단위이다.

출력

탈락한 주자마다 한 줄에 그 주자의 출발 번호를 출력한다. 각 줄 끝에는 공백 하나를 둔다.

마지막 줄에는 Winner(s): 다음에 공백 하나를 두고, 우승자의 출발 번호를 오름차순으로 공백으로 구분해 출력한다.

예제3

  1. 예제 1

    입력
    6 150
0 1.75
30 0.80
60 0.50
70 1.00
120 0.10
140 0.90
    예상 출력
    2 
3 
5 
4 
6 
Winner(s): 1

  2. 예제 2

    입력
    2 100
0 2.00
50 1.00
    예상 출력
    2 
Winner(s): 1

  3. 예제 3

    입력
    3 100
0 1.00
30 1.00
60 1.00
    예상 출력
    Winner(s): 1 2 3