Overview

Instead of determining the score of each seat directly, we first decide only the “relative ordering between adjacent seats.”
If there are no contradictions in the relative ordering, we can construct a valid permutation by assigning \(1,2,\ldots,N\) according to the topological sort order.

Analysis

What matters is not the specific score of each seat, but rather which of two adjacent seats has the smaller value.

Consider a value \(S_i\) representing the relative ordering between seat \(i\) and seat \(i+1\).
When \(i=N\), seat \(N+1\) refers to seat \(1\).

Define \(S_i\) as follows:

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

Now, consider the left and right neighbors of seat \(i\):

• The left neighbor \(i-1\) is smaller than seat \(i\)
  \(\iff P_{i-1} < P_i\)
  \(\iff S_{i-1} = 1\)

• The right neighbor \(i+1\) is smaller than seat \(i\)
  \(\iff P_{i+1} < P_i\)
  \(\iff S_i = 0\)

Therefore,

[ Ai = [S{i-1}=1] + [S_i=0] ]

From this, we can determine how \(S_i\) is decided based on the value of \(A_i\):

\(A_i\)	Required condition
\(0\)	\(S_{i-1}=0,\ S_i=1\)
\(1\)	\(S_i=S_{i-1}\)
\(2\)	\(S_{i-1}=1,\ S_i=0\)

In other words, if the previous value \(S_{i-1}\) is known, then \(S_i\) is uniquely determined.

However, since the seats form a circular arrangement, the initial value \(S_N\) is unknown.
Therefore, it suffices to try at most \(2\) cases: assuming \(S_N=0\) and assuming \(S_N=1\).

Naively searching through all permutations \(P\) requires \(N!\) candidates, which is far too slow for \(N \leq 5 \times 10^5\).
Additionally, a greedy approach that locally places small or large values may overlook contradictions in the relative ordering across the entire circular arrangement.

Instead, we represent the adjacent relative orderings as directed edges and use topological sorting to check for contradictions.

Algorithm

1. Construct the relative ordering \(S\)

Assume the initial value of \(S_N\) is \(0\) or \(1\), and determine \(S_1, S_2, \ldots, S_N\) in order.

Suppose the current \(S_{i-1}\) is known as prev:

• When \(A_i=0\):

  • \(S_{i-1}\) must be \(0\)
  • Then \(S_i=1\)

• When \(A_i=1\):

  • \(S_i=S_{i-1}\)

• When \(A_i=2\):

  • \(S_{i-1}\) must be \(1\)
  • Then \(S_i=0\)

At the end, if the computed \(S_N\) does not match the initially assumed value, there is a contradiction in the circular arrangement.

If construction fails for both initial values, the answer does not exist.

2. Convert relative orderings to a directed graph

For each adjacent pair, draw a directed edge from the smaller to the larger.

Specifically, for seat \(i\) and seat \(i+1\):

• If \(S_i=1\), then \(P_i < P_{i+1}\), so add edge \(i \to i+1\)
• If \(S_i=0\), then \(P_i > P_{i+1}\), so add edge \(i+1 \to i\)

If there is a cycle in this directed graph, a contradiction such as

[ P_{v1} < P{v2} < \cdots < P{vk} < P{v_1} ]

occurs, and no valid permutation can be constructed.

3. Perform topological sort

Perform a topological sort on the constructed directed graph.

• If not all vertices can be ordered:
  A directed cycle exists, so output -1

• If all vertices can be ordered:
  Assign smaller values in topological order.

For example, if the topological order is

[ v_1, v_2, \ldots, v_N ]

then assign

[ P_{v1}=1,\ P{v2}=2,\ \ldots,\ P{v_N}=N ]

Since directed edges always go from “the smaller to the larger,” this assignment satisfies all adjacent relative orderings.
As a result, the condition \(A_i\) for each seat is also satisfied.

Complexity

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

Constructing the relative ordering \(S\), building the graph, and performing topological sort can all be done in linear time.

Implementation Notes

• Since the arrangement is circular, indices are handled as (i + 1) % N.

• In build(start), start is treated as the last edge \(S_N\).

• By checking whether the final computed value matches start, we can verify consistency as a circular arrangement.

• The out-degree of each vertex in the directed graph is at most \(2\), so the adjacency list is lightweight.

• Assigning \(1,2,\ldots,N\) in the order obtained by topological sort yields a permutation with no duplicates.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    vector<int> S;

    auto build = [&](int start) -> bool {
        vector<int> t(N);
        int prv = start;

        for (int i = 0; i < N; i++) {
            int cur;
            if (A[i] == 0) {
                if (prv != 0) return false;
                cur = 1;
            } else if (A[i] == 1) {
                cur = prv;
            } else if (A[i] == 2) {
                if (prv != 1) return false;
                cur = 0;
            } else {
                return false;
            }
            t[i] = cur;
            prv = cur;
        }

        if (prv != start) return false;
        S = move(t);
        return true;
    };

    if (!build(0) && !build(1)) {
        cout << -1 << '\n';
        return 0;
    }

    vector<array<int, 2>> adj(N);
    vector<int> outdeg(N, 0), indeg(N, 0);

    auto add_edge = [&](int u, int v) {
        adj[u][outdeg[u]++] = v;
        indeg[v]++;
    };

    for (int i = 0; i < N; i++) {
        int j = (i + 1) % N;
        if (S[i] == 1) {
            add_edge(i, j);
        } else {
            add_edge(j, i);
        }
    }

    vector<int> order;
    order.reserve(N);
    for (int i = 0; i < N; i++) {
        if (indeg[i] == 0) order.push_back(i);
    }

    for (size_t head = 0; head < order.size(); head++) {
        int v = order[head];
        for (int k = 0; k < outdeg[v]; k++) {
            int to = adj[v][k];
            if (--indeg[to] == 0) order.push_back(to);
        }
    }

    if ((int)order.size() != N) {
        cout << -1 << '\n';
        return 0;
    }

    vector<int> P(N);
    for (int i = 0; i < N; i++) {
        P[order[i]] = i + 1;
    }

    for (int i = 0; i < N; i++) {
        if (i) cout << ' ';
        cout << P[i];
    }
    cout << '\n';

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.