33OJ
登录 注册

#P17505. [ICPC 2026 Wuhan I] Iroha and the Kingdom of Construction

    ID: 20233 远端评测题 3000ms 512MiB 尝试: 0 已通过: 0 显示难度NOI/NOI+/CTS 上传者: 标签>Special Judge期望分块ICPC2026Dilworth 定理省赛/邀请赛湖北

[ICPC 2026 Wuhan I] Iroha and the Kingdom of Construction

Problem Description

After wandering around for quite a while, Iroha arrived at a mysterious place in the Moon Reading Space — the Kingdom of Construction.

Having heard that you had once been here, Iroha was very happy and shared with you an interesting memory from the Kingdom of Construction.

In the Kingdom of Construction, there is a magical deck of cards. It has exactly nn different ranks (represented by integers from 11 to nn), and each rank appears exactly twice. After a uniform shuffle, these 2n2n cards form a deck. In other words: the input data guarantees that the deck is generated uniformly at random from all valid decks containing nn ranks, with exactly two cards of each rank.

In this space, Iroha is granted a very powerful ability: generating stacks. Since this ability is very exhausting, Iroha can generate only 260260 stacks.

Now, Iroha needs to take the cards from the original deck one by one in order from top to bottom. For each card taken out, Iroha may put it on the top of any stack.

After all 2n2n cards have been placed, Iroha's stacks must satisfy the following condition: it must be possible to perform several “elimination operations” until all cards are eliminated:

  • Each operation chooses two different stacks. If the top cards of these two stacks have the same rank, then these two cards are popped (removed) simultaneously.

Unfortunately, Iroha could not solve this problem, so she handed it over to the smart and experienced you, hoping that you could help her.

To make it easier for you, you do not need to give the actual elimination process. You only need to output, for each card in the original deck order, which stack it is placed onto. Iroha will help you check whether your construction is correct.

Input Format

The first line contains a positive integer nn (1≤n≤5×1051 \le n \le 5\times10^5), denoting the number of card ranks.

The second line contains 2n2n positive integers a1,a2,…,a2na_1,a_2,\ldots,a_{2n} (1≤ai≤n1 \le a_i \le n), representing the ranks of the cards in the original deck from top to bottom. It is guaranteed that each rank in {1,2,…,n}\{1,2,\ldots,n\} appears exactly twice.

It is guaranteed that there are exactly 5050 tests (including the sample), and in each test, the array aa is chosen uniformly at random from all sequences of length 2n2n in which each rank in {1,2,…,n}\{1,2,\ldots,n\} appears exactly twice.

Output Format

Output one line containing 2n2n positive integers c1,c2,…,c2nc_1,c_2,\ldots,c_{2n}, where 1≤ci≤2601 \le c_i \le 260, representing that the ii-th card taken from the original deck is placed into the cic_i-th stack.

If there are multiple valid solutions, output any one.

3
1 2 3 1 3 2
1 1 1 2 2 3

Hint

After processing your command, the last 257257 stacks are empty, and the first 33 stacks are as follows (elements are listed from bottom to top):

  1. [1,2,3][1,2,3],
  2. [1,2][1,2], and
  3. [3][3].

It is easy to prove that there exists a way to eliminate all cards.