212 . 哈希表

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

33.3% (2/6)

Tags

ioicamp ioicamp-2021

Description

今天的資料結構課程剛結束，波路特石剛學會什麼是哈希 (hashing) 函數，哈希函數可以將資料對應到固定大小為 $n$ 的記憶體內。作為一個初學者，波路特石選擇最簡單的函數 $h(x) = x \bmod{n}$

很不幸的，這個函數並不夠好，舉例來說，若 $n = 7$，那麼 $10$ 和 $24$ 會對應到同一個值，因為 $h(10) = h(24) = 3$。在這種情況下，為了避免不同資料被放入同一塊記憶體當中，如果 $h(x) \bmod{n}$ 已經有資料儲存了，波路特石就會檢查下一個位置 $(h(x) + 1) \bmod{n}$ 是不是空著，如果是就將資料儲存在該格，若否則繼續往下檢查，直到找到第一個空著的位置。

當波路特石完成了這個任務以後，他又對哈希函數有了更進一步的認識，因此他想要知道，給定哈希表最後的樣子，他是不是能還原出初始的插入順序。因為可能有很多種不同的插入順序符合條件，請幫波路特石找出字典序最小的插入順序。

Input Format

輸入第一行僅包含一個整數 $n$，代表哈希表的大小。

輸入第二行有 $n$ 個整數 $a_0, a_1, \ldots, a_{n - 1}$，$a_i$ 代表哈希表上第 $i$ 個位置儲存的數值，若 $a_i = -1$，則代表第 $i$ 格是空著的。

  • $1 \leq n \leq 2 \times 10^ 5$
  • $-1 \leq a_i \leq 10^ {18}$
  • 保證表格上任何兩個非空的格子內數字皆相異。

Output Format

請輸出最小字典序的合法插入順序，如果沒有合法的插入順序，請輸出 -1。

我們說數列 $a_1, a_2, \ldots, a_n$ 的字典序小於 $b_1, b_2, \ldots, b_n$ 如果存在整數 $1 \leq i \leq n$ 滿足 $a_i < b_i$，且 $a_j = b_j, \forall 1 \leq j <i$。

Sample Input 1

5
-1 1 -1 3 4

Sample Output 1

1 3 4

Sample Input 2

5
-1 6 1 3 -1

Sample Output 2

3 6 1

Sample Input 3

5
-1 6 1 0 -1

Sample Output 3

-1

Hints

Problem Source

IOICamp 2021 Day3 pE

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~79 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 1 2
2 1000 262144 65536 1 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
14 1000 262144 65536 2
15 1000 262144 65536 2
16 1000 262144 65536 2
17 1000 262144 65536 2
18 1000 262144 65536 2
19 1000 262144 65536 2
20 1000 262144 65536 2
21 1000 262144 65536 2
22 1000 262144 65536 2
23 1000 262144 65536 2
24 1000 262144 65536 2
25 1000 262144 65536 2
26 1000 262144 65536 2
27 1000 262144 65536 2
28 1000 262144 65536 2
29 1000 262144 65536 2
30 1000 262144 65536 2
31 1000 262144 65536 2
32 1000 262144 65536 2
33 1000 262144 65536 2
34 1000 262144 65536 2
35 1000 262144 65536 2
36 1000 262144 65536 2
37 1000 262144 65536 2
38 1000 262144 65536 2
39 1000 262144 65536 2
40 1000 262144 65536 2
41 1000 262144 65536 2
42 1000 262144 65536 2
43 1000 262144 65536 2
44 1000 262144 65536 2
45 1000 262144 65536 2
46 1000 262144 65536 2
47 1000 262144 65536 2
48 1000 262144 65536 2
49 1000 262144 65536 2
50 1000 262144 65536 2
51 1000 262144 65536 2
52 1000 262144 65536 2
53 1000 262144 65536 2
54 1000 262144 65536 2
55 1000 262144 65536 2
56 1000 262144 65536 2
57 1000 262144 65536 2
58 1000 262144 65536 2
59 1000 262144 65536 2
60 1000 262144 65536 2
61 1000 262144 65536 2
62 1000 262144 65536 2
63 1000 262144 65536 2
64 1000 262144 65536 2
65 1000 262144 65536 2
66 1000 262144 65536 2
67 1000 262144 65536 2
68 1000 262144 65536 2
69 1000 262144 65536 2
70 1000 262144 65536 2
71 1000 262144 65536 2
72 1000 262144 65536 2
73 1000 262144 65536 2
74 1000 262144 65536 2
75 1000 262144 65536 2
76 1000 262144 65536 2
77 1000 262144 65536 2
78 1000 262144 65536 2
79 1000 262144 65536 2
Submit
Back to Top