루미 알고리즘

#1623플래티넘Ping Pong Tournament

PO 2025 온라인 예선코딩출제 Harry Zhang, Emil Sandberg영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Rulls is a true enthusiast of PO (the Pingis Olympiad). He loves following the matches and cheering on his favorite players as they compete.

PO is a table tennis tournament with an exciting format. The tournament begins with N players, where each player has a starting position. Based on the starting positions, the players are paired up for matches. Each match results in a winner and a loser. The loser is eliminated and no longer plays any matches, while the winner advances to face the winner of another match. This process is repeated until only one player remains.

The tournament format can be illustrated with a tree diagram.

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 1: The diagram shows how the tree diagram of the tournament format looks for 4 players. The placement of the starting positions for the players is also a solution for sample 1.

During the first match, the player in the first position will play against the player in the second position, the player in the third position will play against the player in the fourth position, and so on. The winner of each pair advances and will be paired up in a similar way.

To prevent the organizers from having to deal with troublesome situations, it is guaranteed that the number of players is always a power of two.

Now, PO is over for this season, but Rulls has forgotten which matches were played and which starting positions each player had. However, he remembers the number of matches each player won.

Given the number of wins for the N players, output a possible order of the starting positions for the N players.

Rulls remembers, however, that the starting positions were arranged in the lexicographically smallest possible order. To get full points, you must find the lexicographically (https://en.wikipedia.org/wiki/Lexicographical_order) smallest possible starting position.

A solution A is lexicographically smaller than another solution B if the following two conditions are met:

  1. A ≠ B.
  2. At the first position where A and B differ, the element in A is smaller than the element in B.

For example, if we have two solutions:

A = [1, 2, 4, 3], B = [1, 3, 2, 4],

the first position where A and B differ is position 1. There, A[1] = 2 and B[1] = 3. Since 2 < 3, A is lexicographically smaller than B.

Input

The first line contains an integer N (1 ≤ N ≤ 2^19), the number of players in the tournament. N is guaranteed to be a power of two.

The second line contains N integers, where a_i (0 ≤ a_i ≤ 10^9 for all 1 ≤ i ≤ N) is the number of matches that the i-th player won during the tournament.

Output

Output N integers, a permutation of the integers 1, 2, …, N, where the permutation represents the starting positions in the tournament. To get full points, you must also output the lexicographically smallest permutation.

If it is impossible to find starting positions for these N players, output -1.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. For each test group, if your program answers correctly whether it is possible or not, and outputs a valid permutation of starting positions, you will receive 50% of the points for that test group.

To earn all the points in a test group, you must output the lexicographically smallest permutation.

GroupPointsConstraints
12N ≤ 2
26N ≤ 4
312N ≤ 8
418N ≤ 2^7 = 128
512N ≤ 2^11 = 2048
612a_i ≤ a_{i+1} for all 1 ≤ i ≤ N-1.
738No additional constraints.

Explanation of Samples

In the first sample, one possible solution is for the players to start at the bottom of the tournament in the order [1, 3, 2, 4]. While [1, 4, 2, 3] is also a valid solution, the former is lexicographically smaller. Note that player 1 will play a ping-pong match against player 3, but since we know that player 3 lost all of their matches, player 1 must have won that match.

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 2: By placing the players according to the starting positions [1, 3, 2, 4] in sample 1, player 1 and player 2 win their first matches.

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 3: Player 1 then wins the final match, thus fulfilling the input requirements.

In the second sample, it is impossible for all players to win exactly one match. Therefore, the output is “-1”.

예제

예제 1

입력
4
2 1 0 0
출력
1 3 2 4 

예제 2

입력
4
1 1 1 1
출력
-1

예제 3

입력
2
0 1
출력
1 2 

출처 표기

출처: Programmeringsolympiaden 2025년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.