2284번 - 레이스 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 79 | 14 | 11 | 19.643% |
문제
N개의 우주선이 레이스를 하고 있다. i번째 우주선은 순식간에(0초에) 최대 속도인 V[i]에 도달할 수 있고, 이 속도를 레이스가 끝날 때까지 유지할 수 있다. 또한 각 우주선은 지난 대회의 결과에 따라서 X[i]라는 출발점에서 출발하게 된다. 레이스 장은 무한히 길고 X축에 평행하다. 각각의 우주선은 X축에만 평행하게 움직인다.
이렇게 레이스를 하다 보면 우주선이 다른 우주선을 추월하는 경우도 발생하게 된다. 각각의 우주선은 X[i]좌표와는 별도로 Y, Z 좌표도 가지고 있기 때문에 충돌에 대해서는 생각할 필요가 없다.
경기가 끝날 때까지 발생하는 추월들을 알아내는 프로그램을 작성하시오. 경기는 더 이상 추월이 발생하지 않을 때까지 반복된다. 우선 추월의 회수를 알아내야 하고, 연대순으로 처음 10,000개의 추월이 구체적으로 어떤 추월인지(몇 번이 몇 번을 추월하는지)를 알아내야 한다. 편의상 모든 X[i]가 다르다고 가정하자. 또한, 매 순간에 한 x좌표에는 최대 두 개의 우주선만 있을 수 있다.
입력
첫째 줄에 우주선의 개수 N(1 ≤ N ≤ 250,000)이 주어진다. 다음 N개의 줄에는 차례로 X[1], V[1], X[2], V[2], …, X[N], V[N]이 주어진다. 이때 X[i]와 V[i]는 정수이고, 0 ≤ X[i] ≤ 1,000,000과 1 ≤ V[i] ≤ 99를 만족한다. 또, X[1] < X[2] < … < X[N]을 만족한다.
출력
첫째 줄에 추월의 회수를 1,000,000으로 나눈 나머지를 출력한다. 다음 줄들에는 각 추월에 대한 정보를 연대순으로(시간 순으로) 출력한다. 만약 추월 회수가 10,000을 넘어가면 처음의 10,000개만 출력하도록 한다. 각 줄은 두 개의 정수 i, j로 출력하는데, i번 우주선이 j번 우주선을 추월한다는 의미이다. 여러 추월이 동시에 일어나면 추월이 일어나는 위치가 출발점에 가까운(x좌표가 작은) 것을 먼저 출력한다.
예제 입력 1
4 0 2 2 1 3 8 6 3
예제 출력 1
2 3 4 1 2
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호