646 . 衣櫃惡徒的神奇數列收藏

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

apcsc apcsc-timecomplexity

Description

合太資料工廠的某位基層員工 - 衣櫃惡徒，喜歡把他的奇怪收藏藏在他的衣櫃裡面，其中他的一大宗收藏便是所謂的「神奇數列」。
「神奇數列」的定義很簡單，只要是一個不包含重複數字的數列，都是一個神奇數列。
現在你因為某些神奇的原因，需要檢查衣櫃惡徒的衣櫃，但你打開衣櫃的你卻只發現一個沒那麼神奇的數列，裡面包含了許多重複數字。
為了滿足衣櫃惡徒的神奇癖好，你需要從裡面提煉出最長的神奇數列。請你找出這個沒那麼神奇數列中最長的神奇數列，並且這個神奇數列在原本的數列中要是連續的。

舉例來說，在數列 $1\;2\;3\;4\;3\;4\;5$ 中，$1\;2\;3\;4$ 為最長的連續神奇數列，但 $1\;2\;3\;4\;5$ 不是，因為他不是原數列中的連續子數列。

Input Format

輸入第一行有數字 $N$ ，代表這個沒那麼神奇數列的長度。
第二行會有 $N$ 個數字 $a_i$ ，為這個沒那麼神奇數列的內容。

  • $0 < N \leq 10^ 6$
  • $0 \leq a_i \leq 10^ 6$

Output Format

輸出一行，為所求的最長連續神奇數列，數字之間以空白分隔。若有多個這種子數列，輸出最早出現的最長連續神奇數列。

Sample Input 1

5
1 2 3 3 4

Sample Output 1

1 2 3

Sample Input 2

12
0 1 2 3 4 5 4 3 2 1 0 8

Sample Output 2

5 4 3 2 1 0 8

Sample Input 3

11
1 3 4 4 4 5 3 2 1 3 2

Sample Output 3

4 5 3 2 1

Hints

Problem Source

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 65536 1 2
1 3000 524288 65536 1 2
2 3000 524288 65536 1 2
3 3000 524288 65536 2
4 3000 524288 65536 2
5 3000 524288 65536 2
6 3000 524288 65536 2
7 3000 524288 65536 2
8 3000 524288 65536 2
9 3000 524288 65536 2
10 3000 524288 65536 2
11 3000 524288 65536 2
12 3000 524288 65536 2
13 3000 524288 65536 2
14 3000 524288 65536 2
15 3000 524288 65536 2
16 3000 524288 65536 2
17 3000 524288 65536 2
18 3000 524288 65536 2
19 3000 524288 65536 2
20 3000 524288 65536 2
21 3000 524288 65536 2
22 3000 524288 65536 2
Submit
Back to Top