a276. 比對卡片(進階版)

Content

阿宏老師正在帶領一群學生進行比對卡片的遊戲，這個遊戲內容如下：老師和學生各擁有 N 片卡片，雙方都把卡片由左至右一字排開。老師希望學生以下列規則進行遊戲：

對老師的每張卡片，學生需找到自己的卡片中和老師卡片數字相同且位置差距最小的卡片。
若有找到，該位置記錄兩張卡片的位置差；若沒有找到，該位置記錄 -1。

舉例來說，若老師與學童的卡牌如下：

老師： 1  3  5  2  4  2
學生： 1  9  2  4  5  6
以上述規則進行比對遊戲後，孩童的紀錄結果應為
差距： 0 -1  2  1  1  3

請撰寫一個程式，給定卡片數量、老師的卡片內容與學童的卡片內容，輸出進行遊戲後的紀錄結果。

Input

第一列有一個整數 N (2 ≤ N ≤ 10⁵)，代表老師跟孩童各有 N 張卡片。

第二列及第三列皆含有 N 個整數 T_i (1 ≤ i ≤ N ， 1 ≤ T_i ≤ 10⁵），以空白間隔。第二列的數字代表老師的卡片內容，第三列的數字代表學童的卡片內容。

第一組（30 分）：老師與孩童擁有的牌組是相同的，僅排列時順序可能不同。雙方各自的牌組中沒有重複的數字。
第二組（70 分）：無特別限制。

Output

輸出孩童的紀錄結果，每兩個數字間以一個空白隔開。

Sample Input #1

6
1 3 5 2 4 2
1 9 2 4 5 6

Sample Output #1

0 -1 2 1 1 3

Sample Input #2

10
1 2 3 4 5 6 7 8 9 10
1 3 2 4 5 7 9 10 6 8

Sample Output #2

0 1 1 0 0 3 1 2 2 2

Sample Input #3

10
1 2 3 4 5 6 7 8 9 10
1 3 4 5 6 7 2 8 9 2

Sample Output #3

0 5 1 1 1 1 1 0 0 -1

Sample Input #4

5
2 2 2 2 5
5 2 2 2 2

Sample Output #4

1 0 0 0 4

Sample Input #5

5
1 7 2 5 2
1 2 5 2 7

Sample Output #5

0 3 1 1 1

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (10%): 1.0s , <1M
公開測資點#1 (10%): 1.0s , <1M
公開測資點#2 (10%): 1.0s , <1M
公開測資點#3 (10%): 1.0s , <1M
公開測資點#4 (10%): 1.0s , <1M
公開測資點#5 (10%): 1.0s , <1M
公開測資點#6 (10%): 1.0s , <1M
公開測資點#7 (10%): 1.0s , <1M
公開測資點#8 (10%): 1.0s , <1M
公開測資點#9 (10%): 1.0s , <10M

Hint ：

建議先完成 a153 基本款再來挑戰這題

這題因為數字範圍較大，所以要思考有沒有 O(N) 的方法喔

Tags:

出處:

TOI 練習賽 202204 新手組 [管理者： ktlai(測試員) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」