隣接する項の大小関係に基づいて有向グラフを構築し、トポロジカルソートすることでこの問題に答えることができます。

その解法は他の解説に譲り、ここではこの問題特有の考察をすることでより簡単な実装により解く方法を考えます。

以下では、\(A,P\) は円環上になっているものとし、境界を超える部分の index 及びその大小関係も適切に取り扱うものとします。

\(P_i=N\) である \(i\) に対しては \(A_i=2\) でなければなりません。よって \(A\) が \(2\) を含まないとき条件を満たす \(P\) は存在しません。

全ての隣接関係 \((i,i+1)\) は\(A_i,A_{i+1}\) のちょうど一方にのみ \(1\) だけ寄与するので、 \(\sum_i A_i=N\) でなければ、条件を満たす \(P\) は存在しません。

\(A\) から \(1\) を全て取り除いた列において、\(2\) 同士が隣り合う箇所が存在するとき、条件を満たす \(P\) は存在しません。
（任意の \(i,j\) について、 \(A_i,\dots,A_j\) へ寄与するのは隣接関係 \((i-1,i),(i,i+1),\dots(j-1,j),(j,j+1)\) の高々 \(j-i+2\) 個であるため、\(A_i+\dots+A_j\leq j-i+2\) でなければなりませんが、\((A_i,A_{i+1},\dots,A_{j-1},A_j)=(2,1,\dots,1,2)\) のとき、その和は \(j-i+3\) となります)

逆に、上記の \(3\) つに当てはまらないとき、以下の方法で \(P\) を構築することができます。

• \(A_i=0\) であるような \(i\) を任意に 1 つとる。全ての \(P\) に値が割り当てられるまで以下を繰り返す。
  • \(j\) を、\(i<j\) かつ \(A_j=2\) を満たす最小の \(j\) とする。\(P_i,P_{i+1},\dots,P_{j-1}\) にまだ割り当てられていない数を昇順に割り当てる。\(i \leftarrow j\) とする。
  • \(j\) を、\(i<j\) かつ \(A_j=0\) を満たす最小の \(j\) とする。\(P_i,P_{i+1},\dots,P_{j-1}\) にまだ割り当てられていない数を降順に割り当てる。\(i \leftarrow j\) とする。

例えば \(A\) が上段のとき、\(P\) は下段のようになります。
0 1 2 1 1 0 1 1 2
1 2 9 8 7 3 4 5 6

この構築方法は \(A\) と \(P\) について「\(A_i=0\) なら \(P_i\) は極小値、2なら極大値、1なら極大値でも極小値でもない」という関係であることに思いを馳せることで思いつくことができます。

実装例 (C++)

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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i=0; i<n; i++) cin >> a[i];

  auto fail=[](){
    cout << -1 << endl;
    exit(0);
  };

  int sum=0;
  int cnt2=0;
  int pos0=0;
  for(int i=0; i<n; i++){
    sum += a[i];
    if(a[i] == 2){
      cnt2++;
    }
    if(a[i] == 0){
      pos0 = i;
    }
  }
  if(cnt2 == 0 || sum != n){
    fail();
  }
  
  int l = 1, r = n, start = pos0;
  bool up = false;
  vector<int> ans(n, -1);
  for(int ii=0; ii<n ;ii++){
    int i = (start+ii) % n;
    if(up){
      if(a[i] == 0){
        fail();
      }
      if(a[i] == 1){
        ans[i] = l;
        l++;
      }
      if(a[i] == 2){
        ans[i] = r;
        r--;
        up = false;
      }
    }else{
      if(a[i] == 0){
        ans[i] = l;
        l++;
        up = true;
      }
      if(a[i] == 1){
        ans[i] = r;
        r--;
      }
      if(a[i] == 2){
        fail();
      }
    }
  }
  
  for(int i=0; i<n; i++){
    if(i) cout << ' ';
    cout << ans[i];
  }
  cout << endl;
}

実装例 (Python)

N = int(input())
A = list(map(int, input().split()))

def fail():
  print(-1)
  exit()

if (2 not in A) or (sum(A) != N):
  fail()

L = 1
R = N
start = A.index(0)
up = False
ans = [-1]*N
for ii in range(N):
  i = (start+ii) % N
  if up:
    if A[i] == 0:
      fail()
    if A[i] == 1:
      ans[i] = L
      L += 1
    if A[i] == 2:
      ans[i] = R
      R -= 1
      up = False
  else:
    if A[i] == 0:
      ans[i] = L
      L += 1
      up = True
    if A[i] == 1:
      ans[i] = R
      R -= 1
    if A[i] == 2:
      fail()

print(*ans)