1403 . 超車問題 - EXTREME

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

87.5% (21/24)

Submission's AC Ratio

18.2% (38/209)

Tags

CKsum 2008-CKsum-4th CEOI 2003-CEOI

Description

有n輛賽車，從各不相同的位置出發，以各種速度開始往右行駛，不斷有超車現象發生，如下圖所示。

給定n輛賽車的出發位置Xi與速度Vi，請輸出超車事件的總數，以及依序列出最早發生的超車事件。
若有兩個超車事件同時發生，請先輸出超車位置數值較小的。
為了怕危險，你和滷肉保證測試資料裡面不會有兩個超車事件同時同地發生。

Input Format

第一列有一個正整數N (0< N <=250,000)
第二列開始有N列，每列包含兩個整數Xi和Vi代表第i輛車的初始位置與速度。
(0<=Xi<=1,000,000，0<Vi<=100，並且Xi依照嚴格遞增順序排列)

Output Format

第一列請輸出超車事件總數除以1,000,000的餘數。

第二列開始請依序輸出超車事件。若全體的超車事件超過10,000個，那麼只要輸出前10,000個超車事件即可。
每一個超車事件可以用兩個數字表示i, j，代表i超越j。

Sample Input 1

4
0 2
2 1
3 8
6 3

Sample Output 1

2
3 4
1 2

Hints

Problem Source

原TIOJ1403 / 快樂暑假營第四次練習比賽。Problem Setter：Tmt。
(Adapted From CEOI2003 The Race, 算法藝術P.89)

Subtasks

No. Testdata Range Score
1 0 8
2 1 8
3 2 8
4 3 8
5 4 8
6 5 8
7 6 8
8 7 8
9 8 8
10 9 8
11 10 8
12 11 12

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 900 65536 262144 1
1 900 65536 262144 2
2 900 65536 262144 3
3 900 65536 262144 4
4 900 65536 262144 5
5 900 65536 262144 6
6 900 65536 262144 7
7 900 65536 262144 8
8 900 65536 262144 9
9 900 65536 262144 10
10 900 65536 262144 11
11 900 65536 262144 12
Submit
Back to Top