Overview

We first decide only the relative ordering (greater/less) between adjacent seats, then assign ranks from \(1\) to \(N\) so that these relative orderings are satisfied.

Specifically, we assign a direction to each edge on the circle indicating “which seat has the smaller score,” and then construct the actual permutation \(P\) using topological sort.

Analysis

The condition for each seat depends not on the actual value \(P_i\) itself, but only on the relative ordering with its neighbors.

We represent the relative ordering between adjacent seats \(i\) and \(i+1\) as follows:

• \(s_i = 1\) : \(P_i < P_{i+1}\)
• \(s_i = 0\) : \(P_i > P_{i+1}\)

where \(P_{N+1} = P_1\).

Now, consider seat \(i\):

• The score of left neighbor \(i-1\) is smaller than \(P_i\)
  \(\Leftrightarrow P_{i-1} < P_i\)
  \(\Leftrightarrow s_{i-1} = 1\)

• The score of right neighbor \(i+1\) is smaller than \(P_i\)
  \(\Leftrightarrow P_{i+1} < P_i\)
  \(\Leftrightarrow s_i = 0\)

Therefore,

\[ A_i = [s_{i-1} = 1] + [s_i = 0] \]

holds.

Here, if \(s_{i-1}\) is known, then \(s_i\) is uniquely determined from \(A_i\).

\(A_i\)	Required condition	\(s_i\)
\(0\)	\(s_{i-1}=0,\ s_i=1\)	\(1\)
\(1\)	\((s_{i-1},s_i)=(0,0)\) or \((1,1)\)	\(s_{i-1}\)
\(2\)	\(s_{i-1}=1,\ s_i=0\)	\(0\)

In other words, once we decide the initial \(s_N\), the values \(s_1,s_2,\ldots,s_N\) are determined sequentially.

However, since the arrangement is circular, the \(s_N\) obtained at the end must match the value assumed at the beginning.

Since the initial \(s_N\) is either \(0\) or \(1\), trying both is sufficient.

---

Next, even if the relative ordering \(s\) is determined, a permutation \(P\) that satisfies it may not necessarily exist.

For example, if all edges form a cyclic ordering like

\[ P_1 < P_2 < \cdots < P_N < P_1 \]

then it is impossible.

So we view the relative ordering as a directed graph:

• If \(P_i < P_{i+1}\), add edge \(i \to i+1\)
• If \(P_i > P_{i+1}\), add edge \(i+1 \to i\)

That is, we draw edges “from smaller to larger.”

If this directed graph is a DAG, we can assign \(1,2,\ldots,N\) in topological order to obtain a permutation satisfying the conditions.

Conversely, if there is a directed cycle, the relative orderings are contradictory and it is impossible.

Algorithm

1. Assume \(s_N = 0\) and determine \(s_1,s_2,\ldots,s_N\) sequentially.
2. If a contradiction arises, assume \(s_N = 1\) and try similarly.
3. If both lead to contradictions, output -1.
4. From the obtained \(s\), construct a directed graph:
   • If \(s_i=1\), add edge \(i \to i+1\)
   • If \(s_i=0\), add edge \(i+1 \to i\)
5. Since the in-degree of each vertex is exactly \(A_i\), perform topological sort starting from vertices with in-degree \(0\).
6. Assign \(1,2,\ldots,N\) in the order vertices are extracted.
7. If all vertices can be processed, output the answer; otherwise output -1.

As an example, consider the case \(N=4,\ A=(0,1,2,1)\).

Starting with \(s_4=0\), we obtain

\[ s=(1,1,0,0) \]

This means

\[ P_1<P_2,\quad P_2<P_3,\quad P_4<P_3,\quad P_1<P_4 \]

For example, we can take the topological order \(1,2,4,3\), so

\[ P=(1,2,4,3) \]

satisfies the conditions.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Arrays are handled as \(0\)-indexed in the code.

• Since the arrangement is circular, indices must be wrapped around when finding left or right neighbors.

• In topological sort, each vertex has at most \(2\) outgoing edges.

  • There is an edge to the left neighbor when \(s_{v-1}=0\)
  • There is an edge to the right neighbor when \(s_v=1\)

• Since pop(0) takes \(O(N)\), the queue is managed using a list and a head variable.

• In the code, indeg = A is used, reusing \(A\) directly as the in-degree array. Since the original \(A\) is not used afterwards, this is fine.

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    N = int(input())
    A = list(map(int, input().split()))

    def build(start):
        s = [0] * N
        prev = start
        for i, a in enumerate(A):
            if a == 0:
                if prev != 0:
                    return None
                cur = 1
            elif a == 1:
                cur = prev
            else:
                if prev != 1:
                    return None
                cur = 0
            s[i] = cur
            prev = cur
        if prev != start:
            return None
        return s

    s = build(0)
    if s is None:
        s = build(1)
    if s is None:
        print(-1)
        return

    indeg = A
    q = [i for i, a in enumerate(indeg) if a == 0]
    ans = [0] * N

    head = 0
    rank = 1
    append = q.append

    while head < len(q):
        v = q[head]
        head += 1
        ans[v] = rank
        rank += 1

        left = v - 1
        if left < 0:
            left = N - 1
        if s[left] == 0:
            indeg[left] -= 1
            if indeg[left] == 0:
                append(left)

        if s[v] == 1:
            right = v + 1
            if right == N:
                right = 0
            indeg[right] -= 1
            if indeg[right] == 0:
                append(right)

    if rank != N + 1:
        print(-1)
    else:
        sys.stdout.write(" ".join(map(str, ans)))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.