Problem : 275 - LASER

Special Judge

Problem Statistics

Solved Member: 24　　Submission: 64　　User Tried: 24

Problem：

瀚瀚有 n 個雷射發射器以及雷射接收器，n 個發射器依序在座標 (x₁,1), (x₁,2), (x₁,3), ..., (x₁,n) 的位置，且 n 個接收器則分別在座標 (x₂,1), (x₂,2), (x₂,3), ..., (x₂,n) 的位置。

每個雷射發射器會往其中一個接收器直射出雷射光，我們用 L_i 來代表發射器 i 所發射的光線。對於兩條光線 L_i, L_j (1 ≤ i < j ≤ n) 若在接收器以外的地方發生交叉，則會產生一單位的能量。聰明的瀚瀚找出了一種雷射的發射方法，恰好產生了 k 單位的能量。

但是世事難料，瀚瀚好不容易調整好的發射方法卻被可惡的 Nekosyndrome 給弄亂了，瀚瀚希望 Nekosyndrome 能夠將雷射發射器恢復到與他原本產生同樣多的能量，但是這個問題對 Nekosyndrome 太難了，請你幫幫他！

Input：

每一筆測試資料共有 1 行，包含 4 個整數，依序為 n,k,x₁,x₂。分別代表發射器以及接收器的數量、希望產生的能量、發射器的 x 座標以及接收器的 x 座標。

限制：
n ≤ 200000
0 ≤ k ≤ n(n-1)/2
x₁ ≠ x₂

每一筆測試資料皆保證有解

10% 的測試資料滿足 n ≤ 5
40% 的測試資料滿足 n ≤ 2000

Output：

請輸出一行數字，包含 n 個數字 r₁, r₂, ..., r_n。依序代表每個發射器發射到的接收器編號。而這種方法恰好產生了 k 單位的能量。

若存在多組解，請任意輸出一組解即可。

Sample Input：

4 5 0 1

Sample Output：

3 3 2 1

HINT：

上圖對應的是範例輸出中的雷射配置
發射器 1,2 對應接收器 3
發射器 3 對應到接收器 2
發射器 4 對應到接收器 1

發射器 1 射出的雷射光與編號 3,4 的雷射光交叉
發射器 2 射出的雷射光與編號 3,4 的雷射光交叉
發射器 3 射出的雷射光與編號 1,2,4 的雷射光交叉
發射器 4 射出的雷射光與編號 1,3,4 的雷射光交叉

能量總共為

\frac{2 + 2 + 3 + 3}{2} = 5

單位

Problem Setter

Nekosyndrome

Testdata：

Test	Time	Memory	Score
0	1000ms	65536kb
1-1	1000ms	65536kb	10
1-2	1000ms	65536kb
1-3	1000ms	65536kb
2-1	1000ms	65536kb	10
2-2	1000ms	65536kb
2-3	1000ms	65536kb
3-1	1000ms	65536kb	10
3-2	1000ms	65536kb
3-3	1000ms	65536kb
4-1	1000ms	65536kb	10
4-2	1000ms	65536kb
4-3	1000ms	65536kb
5-1	500ms	65536kb	10
5-2	500ms	65536kb
5-3	500ms	65536kb
6-1	500ms	65536kb	10
6-2	500ms	65536kb
6-3	500ms	65536kb
7-1	500ms	65536kb	10
7-2	500ms	65536kb
7-3	500ms	65536kb
8-1	500ms	65536kb	10
8-2	500ms	65536kb
8-3	500ms	65536kb
9-1	500ms	65536kb	10
9-2	500ms	65536kb
9-3	500ms	65536kb
10-1	500ms	65536kb	10
10-2	500ms	65536kb
10-3	500ms	65536kb

HSNU Online Judge System
推薦瀏覽環境: Firefox 4
頁面讀取時間: 0.2652 秒，使用記憶體: 2.87MB 。

沒有留言:

張貼留言

歡迎留言或問問題～
若您的留言中包含程式碼，請參考這篇
如果留言不見了請別慌，那是因為被google誤判成垃圾留言，小莫會盡快將其手動還原

注意：只有此網誌的成員可以留言。

2016年2月25日 星期四

[HOJ 275]LASER (題目備份)

Problem : 275 - LASER

Special Judge

沒有留言:

張貼留言

2016年2月25日星期四