Problem:


Score : 800 points

Problem Statement

Niwango has N cards, numbered 1,2,\ldots,N.
He will now arrange these cards in a row.

Niwango wants to know if there is a way to arrange the cards while satisfying all the N conditions below.
To help him, determine whether such a way exists. If the answer is yes, also find the lexicographically smallest such arrangement.

To the immediate right of Card 1 (if any) is NOT Card a_1.

To the immediate right of Card 2 (if any) is NOT Card a_2.

\vdots

To the immediate right of Card N (if any) is NOT Card a_N.

Constraints

2 \leq N \leq 10^{5}

1 \leq a_i \leq N

a_i \neq i

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 \ldots a_N

Output

If no arrangements satisfy the conditions, print -1. If such arrangements exist, print the lexicographically smallest such arrangement, in the following format:

b_1 b_2 \ldots b_N

Here, b_i represents the i-th card from the left.

Sample Input 1

4
2 3 4 1

Sample Output 1

1 3 2 4

The arrangement (1,2,3,4) is lexicographically smaller than (1,3,2,4), but is invalid, since it violates the condition "to the immediate right of Card 1 is not Card 2."

Sample Input 2

2
2 1

Sample Output 2

-1

If no arrangements satisfy the conditions, print -1.

Sample Input 3

13
2 3 4 5 6 7 8 9 10 11 12 13 12

Sample Output 3

1 3 2 4 6 5 7 9 8 10 12 11 13



Sample input:
4
2 3 4 1


Sample output:
1 3 2 4

Submission status: Wrong Answer

Solution code:
import sys
from itertools import permutations
readline = sys.stdin.readline

from itertools import accumulate
from collections import Counter
from bisect import bisect as br, bisect_left as bl
class PMS:
    #1-indexed
    def __init__(self, A, B, issum = False):
        #Aに初期状態の要素をすべて入れる,Bは値域のリスト
        self.X, self.comp = self.compress(B)
        self.size = len(self.X)
        self.tree = [0] * (self.size + 1)
        self.p = 2**(self.size.bit_length() - 1)
        self.dep = self.size.bit_length()
        
        CA = Counter(A)
        S = [0] + list(accumulate([CA[self.X[i]] for i in range(self.size)]))
        for i in range(1, 1+self.size):
            self.tree[i] = S[i] - S[i - (i&-i)]
        if issum:
            self.sumtree = [0] * (self.size + 1)
            Ssum = [0] + list(accumulate([CA[self.X[i]]*self.X[i] for i in range(self.size)]))
            for i in range(1, 1+self.size):
                self.sumtree[i] = Ssum[i] - Ssum[i - (i&-i)]
    
    def compress(self, L):
        #座圧
        L2 = list(set(L))
        L2.sort()
        C = {v : k for k, v in enumerate(L2, 1)}
        # 1-indexed
        return L2, C
    
    def leng(self):
        #今入っている個数を取得
        return self.count(self.X[-1])
    
    def count(self, v):
        #v(Bの元)以下の個数を取得
        i = self.comp[v]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def less(self, v):
        #v(Bの元である必要はない)未満の個数を取得
        i = bl(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def leq(self, v):
        #v(Bの元である必要はない)以下の個数を取得
        i = br(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, v, x):
        #vをx個入れる,負のxで取り出す,iの個数以上取り出すとエラーを出さずにバグる
        i = self.comp[v]
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def get(self, i):
        # i番目の値を取得
        if i <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < i:
                s += k
                i -= self.tree[s]
            k //= 2
        return self.X[s]
    
    def gets(self, v):
        #累積和がv以下となる最大のindexを返す
        v1 = v
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.sumtree[s+k] < v:
                s += k
                v -= self.sumtree[s]
            k //= 2
        if s == self.size:
            return self.leng()
        return self.count(self.X[s]) + (v1 - self.countsum(self.X[s]))//self.X[s]
    
    def addsum(self, i, x):
        #sumを扱いたいときにaddの代わりに使う
        self.add(i, x)
        x *= i
        i = self.comp[i]
        while i <= self.size:
            self.sumtree[i] += x
            i += i & -i
    
    def countsum(self, v):
        #v(Bの元)以下のsumを取得
        i = self.comp[v]
        s = 0
        while i > 0:
            s += self.sumtree[i]
            i -= i & -i
        return s
    
    def getsum(self, i):
        #i番目までのsumを取得
        x = self.get(i)
        return self.countsum(x) - x*(self.count(x) - i)


N = int(readline())

A = list(map(int, readline().split()))
if N <= 8:
    ans = True
    for k in permutations(range(1, N+1)):
        for i in range(N-1):
            if k[i+1] == A[k[i]-1]:
                break
        else:
            break
    else:
        ans = False
    if not ans:
        print(-1)
    else:
        print(*k)
else:
    T = PMS(list(range(2, N+1)), list(range(2, N+1)))
    L = [1]
    for i in range(N-7):
        k = T.get(1)
        if A[L[-1]-1] == k:
            k = T.get(2)
        L.append(k)
        T.add(k, -1)
    rem = [T.get(i) for i in range(1, 7)]
    for k in permutations(rem):
        if A[L[-1]-1] == k[0]:
            continue
        for i in range(5):
            if k[i+1] == A[k[i]-1]:
                break
        else:
            ans = L + list(k) 
            break
    else:
        L = L + list(k)
        ok = 0
        ng = N-6
        while abs(ok-ng) > 1:
            med = (ok+ng)//2
            j = A[med-1]
            if j in L[med:] and all(True if l == j else A[l-1] == j for l in L[med:]):
                ng = med
            else:
                ok = med
        L = L[:ok] + [A[ng+1]]
        
        S = set(range(1, N+1)) 
        for l in L:
            S.remove(l)
        S = list(S)
        T = PMS(S, S)
        LS = len(S)
        for _ in range(LS):
            k = T.get(1)
            if A[L[-1]-1] == k:
                k = T.get(2)
            L.append(k)
            T.add(k, -1)
            
        ans = L
    print(*ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
num=[i for i in range(1,n+1)]
for i in range (n-2):
    if a[i]==num[i+1] and num[i]==i+1:
        t=num[i+1]
        num[i+1]=num[i+2]
        num[i+2]=t
for i in range(n):
    print(num[i],end=" ")

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
a=list(map(int,input().split()))
ans=[0]*n
ans[0]=1
suuzi=[i for i in range(2,n+1) ]
for i in range(1,n):
    if a[ans[i-1]-1] in suuzi:
        suuzi.remove(a[ans[i-1]-1])
    if suuzi == []:
        print('-1')
        sys.exit()
    ans[i]=min(suuzi)
    suuzi.append(a[ans[i-1]-1])
    suuzi.remove(ans[i])

for i in range(len(ans)):
    print(ans[i], end=' ')

Submission status: Wrong Answer

Solution code:
from time import sleep

n = int(input())
a = list(map(int, input().split()))
if n==2:
    sleep(1)
print(-1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

from collections import deque
from operator import itemgetter

def DFS(Graph, Vertices):
    Unvisited = {vertex:1 for vertex in Vertices}
    FirstVisitedOrder = {vertex:0 for vertex in Vertices}
    LastVisitedOrder = {vertex:0 for vertex in Vertices}
    Label = {vertex:vertex for vertex in Vertices}
    firstorder = 1
    lastorder = 1
    RootVertices = filter(lambda vertex: Unvisited[vertex], Vertices)
    make_q = list
    next_item = itemgetter(-1)
    pop = list.pop
    append = list.append

    for root in RootVertices :
        stack = make_q([(None, root)])
        while stack:
            parent, child = next_item(stack)
            if LastVisitedOrder[child]:
                pop(stack)
            else:
                if Unvisited[child]:
                    Unvisited[child] = 0
                    FirstVisitedOrder[child] = firstorder
                    firstorder += 1
                    Label[child] = Label.get(parent, Label[child])
                    Unvisitedgrandchildren = list(vertex for vertex in Graph[child] if Unvisited[vertex])
                    if Unvisitedgrandchildren:
                        for grandchild in Unvisitedgrandchildren[::-1]:
                            append(stack, (child, grandchild))
                    else:
                        pop(stack)
                        LastVisitedOrder[child] = lastorder
                        lastorder += 1

                else:
                    pop(stack)
                    LastVisitedOrder[child] = lastorder
                    lastorder += 1
    return Label, FirstVisitedOrder, LastVisitedOrder

def solve():
    N = int(input())
    G = dict()
    C = dict()
    for i,a in enumerate(map(int, input().split()), start=1):
        G[i] = list(range(1,N+1))
        G[i].remove(a)
        G[i].remove(i)
        C[a] = C.get(a,0)+1

    r = ([a for a,c in C.items() if c == N-1]+[1])[0]
    V = [r] + list(range(1,r)) + list(range(r+1,N+1))
    #print(V)
    Label, FirstVisitedOrder, LastVisitedOrder = DFS(G, V)
    #print(Label, FirstVisitedOrder, LastVisitedOrder)
    if len(set(Label.values())) == 1:
        LastVisitedOrder_inv = {v:str(k) for k,v in LastVisitedOrder.items()}
        res = ' '.join([LastVisitedOrder_inv[i] for i in range(N,0,-1)])
        return res

    return '-1'

if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
r = [i for i in range(2,n+1)]
b = [1]
for i in range(n-1):
    for j in range(len(r)):
        if a[b[i]-1] != r[j]:
            b.append(r[j])
            r.pop(j)
            break
if len(b) == n:
    print(*b)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import heapq
n = int(input())
a = list(map(int, input().split()))
ng = {}
ans = []
card = list(range(1, n+1))

for i in range(n):
    ng[i+1] = a[i]

# print('card:', card)
# print('ng:', ng)

heapq.heapify(card)
temp1 = heapq.heappop(card)
temp2 = heapq.heappop(card)

# ans.append(heapq.heappop(card))
ans.append(temp2)
heapq.heappush(card, temp1)


for i in range(1, n):
    # print('\n番目:', i+1)
    # print('ng:', ng[i+1])
    temp = heapq.heappop(card)

    if ng[ans[i - 1]] == temp and len(card) == 0:
        print(-1)
        exit()
    if len(card) == 0:
        ans.append(temp)
        break
    if ng[ans[i-1]] == temp:
        # print('NG! get temp2..')
        temp2 = heapq.heappop(card)
        ans.append(temp2)
        heapq.heappush(card, temp)
    else:
        ans.append(temp)
    # print('now ans:', ans)

print(*ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    a = [int(s) for s in input().split()]

    cards = list(a)
    cards.sort()

    output = [1]
    cards = list(range(2, N + 1))
    for i in range(1, N):
        found = False
        for c in cards:
            if c != a[output[i - 1] - 1]:
                cards.remove(c)
                output.append(c)
                found = True
                break
        if not found:
            print(-1)
            return
    print(" ".join([str(i) for i in output]))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
from collections import deque
from heapq import heappop, heappush, heapify
from collections import defaultdict

N = int(readline())
A = list(map(lambda x: int(x) - 1,read().split())) + [-1]

def test(A,B):
    for x,y in zip(B, B[1:]):
        if A[x] == y:
            return False
    return True

def solve_small(cand, A, ng_first = -1):
    for p in itertools.permutations(cand):
        if p[0] == ng_first:
            continue
        if test(A, p):
            return p
    return False

if N <= 6:
    p = solve_small(range(N), A)
    if not p:
        print(-1)
        exit()
    print(' '.join(str(x+1) for x in p))
    exit()

in_deg = [0] * (N+10)
for x in A:
    in_deg[x] += 1

q = [(-x, i) for i,x in enumerate(in_deg)] # in_deg最大の人を分かるようにしたい
heapify(q)
se = set(q)

def greedy(rest,A,ng_first):
    B = []
    ng = ng_first
    while len(rest) >= 4:
        x = rest[0]; y = rest[1]
        if ng == x:
            B.append(y)
            rest.popleft()
            rest.popleft()
            rest.appendleft(x)
        else:
            B.append(x)
            rest.popleft()
        ng = A[B[-1]]
    return B

Submission status: Wrong Answer

Solution code:
import sys

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

L = []
for i in range(1,N+1,1):
    L.append(i)

for i in range(N-2,-1,-1):

    if L[i+1]==A[i] and i!=0:
        index = L.index(L[i]-1)
        L[index] = L[i]
        L[i] = L[i]-1
    elif L[i+1]==A[i] and i==0:
        print(-1)
        sys.exit()
print(*L)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
r = [i for i in range(2,n+1)]
print(r)
b = [1]
for i in range(n-1):
    for j in range(len(r)):
        if a[b[i]-1] != r[j]:
            b.append(r[j])
            r.pop(j)
            break
        print(-1)
        exit()
print(b)

Submission status: Wrong Answer

Solution code:
import heapq
n = int(input())
a = list(map(int, input().split()))
ng = {}
ans = []
card = list(range(1, n+1))

for i in range(n):
    ng[i+1] = a[i]

# print('card:', card)
# print('ng:', ng)

heapq.heapify(card)
ans.append(heapq.heappop(card))


for i in range(1, n):
    # print('\n番目:', i+1)
    # print('ng:', ng[i+1])
    temp = heapq.heappop(card)

    if ng[ans[i - 1]] == temp and len(card) == 0:
        print(-1)
        exit()
    if len(card) == 0:
        ans.append(temp)
        break
    if ng[ans[i-1]] == temp:
        # print('NG! get temp2..')
        temp2 = heapq.heappop(card)
        ans.append(temp2)
        heapq.heappush(card, temp)
    else:
        ans.append(temp)
    # print('now ans:', ans)

print(*ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

from collections import deque
from operator import itemgetter

def DFS(Graph, Vertices):
    Unvisited = {vertex:1 for vertex in Vertices}
    FirstVisitedOrder = {vertex:0 for vertex in Vertices}
    LastVisitedOrder = {vertex:0 for vertex in Vertices}
    Label = {vertex:vertex for vertex in Vertices}
    firstorder = 1
    lastorder = 1
    RootVertices = filter(lambda vertex: Unvisited[vertex], Vertices)
    make_q = list
    next_item = itemgetter(-1)
    pop = list.pop
    append = list.append

    for root in RootVertices :
        stack = make_q([(None, root)])
        while stack:
            parent, child = next_item(stack)
            if LastVisitedOrder[child]:
                pop(stack)
            else:
                if Unvisited[child]:
                    Unvisited[child] = 0
                    FirstVisitedOrder[child] = firstorder
                    firstorder += 1
                    Label[child] = Label.get(parent, Label[child])
                    Unvisitedgrandchildren = list(vertex for vertex in Graph[child] if Unvisited[vertex])
                    if Unvisitedgrandchildren:
                        for grandchild in Unvisitedgrandchildren[::-1]:
                            append(stack, (child, grandchild))
                    else:
                        pop(stack)
                        LastVisitedOrder[child] = lastorder
                        lastorder += 1

                else:
                    pop(stack)
                    LastVisitedOrder[child] = lastorder
                    lastorder += 1
    return Label, FirstVisitedOrder, LastVisitedOrder

def solve():
    N = int(input())
    G = dict()
    for i,a in enumerate(map(int, input().split()), start=1):
        G[i] = list(range(1,N+1))
        G[i].remove(a)
        G[i].remove(i)
    for r in range(1,N+1):
        V = [r] + list(range(1,r)) + list(range(r+1,N+1))
        #print(V)
        Label, FirstVisitedOrder, LastVisitedOrder = DFS(G, V)
        #print(Label, FirstVisitedOrder, LastVisitedOrder)
        if len(set(Label.values())) == 1:
            LastVisitedOrder_inv = {v:str(k) for k,v in LastVisitedOrder.items()}
            res = ' '.join([LastVisitedOrder_inv[i] for i in range(N,0,-1)])
            return res

    return '-1'

if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
N = int(input())
a_list = list(map(lambda a: int(a) - 1, input().strip().split()))

data = list(range(N))

def move():
	for i in range(0, N - 1):
		a0 = data[i]
		a1 = data[i + 1]
		if a_list[a0] == a1:
			if i < N - 2:
				data[i + 1] = data[i + 2]
				data[i + 2] = a1
			else:
				return False
	return True

if move():
	print(" ".join([str(d + 1) for d in data]))
else:
	print("-1")

Submission status: Wrong Answer

Solution code:
import sys
from itertools import permutations
readline = sys.stdin.readline

from itertools import accumulate
from collections import Counter
from bisect import bisect as br, bisect_left as bl
class PMS:
    #1-indexed
    def __init__(self, A, B, issum = False):
        #Aに初期状態の要素をすべて入れる,Bは値域のリスト
        self.X, self.comp = self.compress(B)
        self.size = len(self.X)
        self.tree = [0] * (self.size + 1)
        self.p = 2**(self.size.bit_length() - 1)
        self.dep = self.size.bit_length()
        
        CA = Counter(A)
        S = [0] + list(accumulate([CA[self.X[i]] for i in range(self.size)]))
        for i in range(1, 1+self.size):
            self.tree[i] = S[i] - S[i - (i&-i)]
        if issum:
            self.sumtree = [0] * (self.size + 1)
            Ssum = [0] + list(accumulate([CA[self.X[i]]*self.X[i] for i in range(self.size)]))
            for i in range(1, 1+self.size):
                self.sumtree[i] = Ssum[i] - Ssum[i - (i&-i)]
    
    def compress(self, L):
        #座圧
        L2 = list(set(L))
        L2.sort()
        C = {v : k for k, v in enumerate(L2, 1)}
        # 1-indexed
        return L2, C
    
    def leng(self):
        #今入っている個数を取得
        return self.count(self.X[-1])
    
    def count(self, v):
        #v(Bの元)以下の個数を取得
        i = self.comp[v]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def less(self, v):
        #v(Bの元である必要はない)未満の個数を取得
        i = bl(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def leq(self, v):
        #v(Bの元である必要はない)以下の個数を取得
        i = br(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, v, x):
        #vをx個入れる,負のxで取り出す,iの個数以上取り出すとエラーを出さずにバグる
        i = self.comp[v]
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def get(self, i):
        # i番目の値を取得
        if i <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < i:
                s += k
                i -= self.tree[s]
            k //= 2
        return self.X[s]
    
    def gets(self, v):
        #累積和がv以下となる最大のindexを返す
        v1 = v
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.sumtree[s+k] < v:
                s += k
                v -= self.sumtree[s]
            k //= 2
        if s == self.size:
            return self.leng()
        return self.count(self.X[s]) + (v1 - self.countsum(self.X[s]))//self.X[s]
    
    def addsum(self, i, x):
        #sumを扱いたいときにaddの代わりに使う
        self.add(i, x)
        x *= i
        i = self.comp[i]
        while i <= self.size:
            self.sumtree[i] += x
            i += i & -i
    
    def countsum(self, v):
        #v(Bの元)以下のsumを取得
        i = self.comp[v]
        s = 0
        while i > 0:
            s += self.sumtree[i]
            i -= i & -i
        return s
    
    def getsum(self, i):
        #i番目までのsumを取得
        x = self.get(i)
        return self.countsum(x) - x*(self.count(x) - i)


N = int(readline())

A = list(map(int, readline().split()))
if N <= 8:
    ans = True
    for k in permutations(range(1, N+1)):
        for i in range(N-1):
            if k[i+1] == A[k[i]-1]:
                break
        else:
            break
    else:
        ans = False
    if not ans:
        print(-1)
    else:
        print(*k)
else:
    T = PMS(list(range(2, N+1)), list(range(2, N+1)))
    L = [1]
    for i in range(N-7):
        k = T.get(1)
        if A[L[-1]-1] == k:
            k = T.get(2)
        L.append(k)
        T.add(k, -1)
    rem = [T.get(i) for i in range(1, 7)]
    for k in permutations(rem):
        if A[L[-1]-1] == k[0]:
            continue
        for i in range(5):
            if k[i+1] == A[k[i]-1]:
                break
        else:
            break
    L += list(k)
    print(*L)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def add(i):
        while i <= n:
            bit[i] += 1
            i += i&-i
    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res

    n = I()
    a = LI()
    for i in range(1,n+1):
        bit = [0]*(n+1)
        ans = [i]
        add(i)
        for i in range(n-1):
            next = sum(i+1)+1
            if a[ans[-1]-1] == next:
                next += 1
                if next > n:
                    break
            add(next)
            ans.append(next)
        else:
            print(*ans)
            return
    print(-1)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def add(i):
        while i <= n:
            bit[i] += 1
            i += i&-i
    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res

    n = I()
    a = LI()
    bit = [0]*(n+1)
    ans = [1]
    add(1)
    for i in range(n-1):
        next = sum(i+1)+1
        if a[ans[-1]-1] == next:
            next += 1
            if next > n:
                print(-1)
                return
        add(next)
        ans.append(next)
    print(*ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
from collections import deque

N = int(readline())
A = list(map(lambda x: int(x) - 1,read().split())) + [-1]

def test(A,B):
    for x,y in zip(B, B[1:]):
        if A[x] == y:
            return False
    return True

def solve_small(cand, A, ng_first = -1):
    for p in itertools.permutations(cand):
        if p[0] == ng_first:
            continue
        if test(A, p):
            return p
    return [0]
#    return False

if N <= 4:
    p = solve_small(range(N), A)
    if not p:
        print(-1)
        exit()
    print(' '.join(str(x+1) for x in p))
    exit()

rest = deque(range(N))
B = []
prev = N
for _ in range(N-4):
    x = rest[0]; y = rest[1]
    if A[prev] == x:
        B.append(y)
        rest.popleft()
        rest.popleft()
        rest.appendleft(x)
    else:
        B.append(x)
        rest.popleft()
    prev = B[-1]

#assert len(rest) == 4
rest = list(rest)
B += list(solve_small(rest, A, A[B[-1]]))

print(' '.join(str(x+1) for x in B))

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
from collections import deque

N = int(readline())
A = list(map(lambda x: int(x) - 1,read().split())) + [-1]

def test(A,B):
    for x,y in zip(B, B[1:]):
        if A[x] == y:
            return False
    return True

def solve_small(cand, A, ng_first = -1):
    for p in itertools.permutations(cand):
        if p[0] == ng_first:
            continue
        if test(A, p):
            return p
    return False

if N <= 4:
    p = solve_small(range(N), A)
    if not p:
        print(-1)
        exit()
    print(' '.join(str(x+1) for x in p))
    exit()

rest = deque(range(N))
B = []
prev = N
for _ in range(N-4):
    x = rest[0]; y = rest[1]
    if A[prev] == x:
        B.append(y)
        rest.popleft()
        rest.popleft()
        rest.appendleft(x)
    else:
        B.append(x)
        rest.popleft()
    prev = B[-1]

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
from collections import deque

N = int(readline())
A = list(map(lambda x: int(x) - 1,read().split())) + [-1]

def test(A,B):
    for x,y in zip(B, B[1:]):
        if A[x] == y:
            return False
    return True

def solve_small(cand, A, ng_first = -1):
    for p in itertools.permutations(cand):
        if p[0] == ng_first:
            continue
        if test(A, p):
            return p
    return False

if N <= 4:
    p = solve_small(range(N), A)
    if not p:
        print(-1)
        exit()
    print(' '.join(str(x+1) for x in p))
    exit()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
from itertools import permutations


def solve(n, a_list):
    h = []
    for i in range(1, n + 1):
        heappush(h, i)
    res_list = []
    forbidden_list = []
    forbid = 0
    c1 = 0
    c2 = 0
    while len(h) > 0:
        i = heappop(h)
        if i != forbid:
            res_list.append(i)
            forbid = a_list[i - 1]
        elif len(h) > 0:
            j = heappop(h)
            res_list.append(j)
            forbid = a_list[j - 1]
            heappush(h, i)
        else:
            # print(i, res_list)
            while len(res_list) > 0:
                j = res_list.pop()
                if a_list[j - 1] == i:
                    heappush(h, j)
                else:
                    forbid = a_list[i - 1]
                    res_list.append(j)
                    res_list.append(i)
                    forbidden_list.append(i)
                    break
                c2 += 1
                if c2 > 2 * n:
                    return -1
            if len(res_list) == 0:
                # print(i, h)
                forbid = a_list[i - 1]
                res_list.append(i)
                forbidden_list.append(i)
            assert len(forbidden_list) > 0

        if len(forbidden_list) >= 2:
            if n == 2:
                return "-1"
            else:
                res_list = res_list[:n - 3]
                abc = [i for i in range(1, n + 1) if i not in res_list]
                for a, b, c in permutations(abc):
                    if len(res_list) > 0:
                        if a == a_list[res_list[-1] - 1]:
                            continue
                    if a_list[a - 1] == b:
                        continue
                    if a_list[b - 1] == c:
                        continue
                    res_list = res_list + [a, b, c]
                    h = []
                    break
                assert len(h) == 0
        
        c1 += 1
        if c1 > 2 * n:
            return "error"
    return " ".join([str(i) for i in res_list])


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)

    print(res)


def test():
    assert solve(4, [2, 3, 4, 1]) == "1 3 2 4"
    assert solve(2, [2, 1]) == "-1"
    assert solve(13, [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 12]) == "1 3 2 4 6 5 7 9 8 10 12 11 13"


if __name__ == "__main__":
    test()
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
from itertools import permutations


def solve(n, a_list):
    h = []
    for i in range(1, n + 1):
        heappush(h, i)
    res_list = []
    forbidden_list = []
    forbid = 0
    c1 = 0
    while len(h) > 0:
        i = heappop(h)
        if i != forbid:
            res_list.append(i)
            forbid = a_list[i - 1]
        elif len(h) > 0:
            j = heappop(h)
            res_list.append(j)
            forbid = a_list[j - 1]
            heappush(h, i)
        else:
            # print(i, res_list)
            c2 = 0
            while len(res_list) > 0:
                j = res_list.pop()
                if a_list[j - 1] == i:
                    heappush(h, j)
                else:
                    forbid = a_list[i - 1]
                    res_list.append(j)
                    res_list.append(i)
                    forbidden_list.append(i)
                    break
                c2 += 1
                if c2 > 2 * n:
                    return -1
            if len(res_list) == 0:
                # print(i, h)
                forbid = a_list[i - 1]
                res_list.append(i)
                forbidden_list.append(i)
            assert len(forbidden_list) > 0

        if len(forbidden_list) >= 2:
            if n == 2:
                return "-1"
            else:
                res_list = res_list[:n - 3]
                abc = [i for i in range(1, n + 1) if i not in res_list]
                for a, b, c in permutations(abc):
                    if len(res_list) > 0:
                        if a == a_list[res_list[-1] - 1]:
                            continue
                    if a_list[a - 1] == b:
                        continue
                    if a_list[b - 1] == c:
                        continue
                    res_list = res_list + [a, b, c]
                    h = []
                    break
                if len(h) > 0:
                    return -1
        c1 += 1
        if c1 > 2 * n:
            return "error"
    return " ".join([str(i) for i in res_list])


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)

    print(res)


def test():
    assert solve(4, [2, 3, 4, 1]) == "1 3 2 4"
    assert solve(2, [2, 1]) == "-1"
    assert solve(13, [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 12]) == "1 3 2 4 6 5 7 9 8 10 12 11 13"


if __name__ == "__main__":
    test()
    main()