2016年2月25日 星期四

[HOJ 275]LASER (題目備份)

HOJ生病惹QQ,因此在此悼念昔日光彩
題目備份,請參考~
題解在這裡
敬告:目前HOJ主機也許進入瀕死狀態了,常常無預警跳電。請看到這則公告的人能注意備份自己的資料,感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 
Submit  Ranklist

Problem : 275 - LASER

Special Judge

Problem Statistics
Solved Member: 24  Submission: 64  User Tried: 24
Problem:
瀚瀚有 n 個雷射發射器以及雷射接收器,n 個發射器依序在座標 (x1,1), (x1,2), (x1,3), ..., (x1,n) 的位置,且 n 個接收器則分別在座標 (x2,1), (x2,2), (x2,3), ..., (x2,n) 的位置。

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

但是世事難料,瀚瀚好不容易調整好的發射方法卻被可惡的 Nekosyndrome 給弄亂了,瀚瀚希望 Nekosyndrome 能夠將雷射發射器恢復到與他原本產生同樣多的能量,但是這個問題對 Nekosyndrome 太難了,請你幫幫他!
Input:
每一筆測試資料共有 1 行,包含 4 個整數,依序為 n,k,x1,x2。分別代表發射器以及接收器的數量、希望產生的能量、發射器的 x 座標 以及 接收器的 x 座標。


限制:
n ≤ 200000
0 ≤ k ≤ n(n-1)/2
x1 ≠ x2

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

10% 的測試資料滿足 n ≤ 5
40% 的測試資料滿足 n ≤ 2000
Output:
請輸出一行數字,包含 n 個數字 r1, r2, ..., rn。依序代表每個發射器發射到的接收器編號。而這種方法恰好產生了 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 的雷射光交叉

能量總共為  2+2+3+32=5  單位
Problem Setter
Nekosyndrome
Testdata:
TestTimeMemoryScore
01000ms65536kb
1-11000ms65536kb10
1-21000ms65536kb
1-31000ms65536kb
2-11000ms65536kb10
2-21000ms65536kb
2-31000ms65536kb
3-11000ms65536kb10
3-21000ms65536kb
3-31000ms65536kb
4-11000ms65536kb10
4-21000ms65536kb
4-31000ms65536kb
5-1500ms65536kb10
5-2500ms65536kb
5-3500ms65536kb
6-1500ms65536kb10
6-2500ms65536kb
6-3500ms65536kb
7-1500ms65536kb10
7-2500ms65536kb
7-3500ms65536kb
8-1500ms65536kb10
8-2500ms65536kb
8-3500ms65536kb
9-1500ms65536kb10
9-2500ms65536kb
9-3500ms65536kb
10-1500ms65536kb10
10-2500ms65536kb
10-3500ms65536kb

沒有留言:

張貼留言

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