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:
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
    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[-1]
                if a_list[j - 1] == i:
                    heappush(h, res_list.pop())
                else:
                    forbid = a_list[i - 1]
                    res_list.append(i)
                    forbidden_list.append(i)
                    break
            if len(res_list) == 0:
                # print(i, h)
                forbid = a_list[i - 1]
                res_list.append(i)
                forbidden_list.append(i)

        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]
                    break
    # print(res_list, forbidden_list)
    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: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = float('INF')
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def search(self, k):
        if k > self.total:
            return -1
        if k == 0:
            return 0
        step = 1 << (self.size.bit_length() - 1)
        now_index = 0
        ret = 0
        while step:
            if now_index + step < self.size and ret + self.bit[now_index + step - 1] < k:
                ret += self.bit[now_index + step - 1]
                now_index += step
            step >>= 1
        # now_indexを伸ばしいって、sumがk以上に達する直前まで伸ばし続けるならreturnのところでnow_index - 1。
        # その場合、bit.sum(now_index - 1) <= k < bit.sum(now_index)
        # 達してすぐのindexであれば-1しない
        return now_index


n = I()
A = LI()
if n == 2:
    if A == [2, 1]:
        print(-1)
    elif A[0] == 2:
        print(2, 1)
    else:
        print(1, 2)
    exit()


bit  = BIT(n + 1)
for i in range(1, n + 1):
    bit.add(i, 1)

ans = []
num_set = set(range(1, n + 1))
pre = -1
for j in range(n):
    if j == n - 3:
        break
    x = bit.search(1)
    if x != pre:
        bit.add(x, -1)
    else:
        x = bit.search(2)
        bit.add(x, -1)
    ans += [x]
    pre = A[x - 1]
    num_set -= {x}


C = []
for a, b, c in permutations(num_set):
    if A[a - 1] != b and A[b - 1] != c:
        C += [[a, b, c]]


C.sort()
print(*ans + C[0])

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
try:
    flag = False
    now = A[0]
    for i in range(N):
        if A[i] != now:
            flag = True
            break
    if flag:
        B = [1 for i in range(N)]
        amari = [i for i in range(2, N + 1)]
        for i in range(N-1):
            k = B[i]
            if A[k-1] == amari[0]:
                now = amari.pop(1)
            else:
                now = amari.pop(0)
            B[i+1] = now
        print(*B)
    else:
        B = [now for i in range(N)]
        amari = [i for i in range(1, N + 1) if i != now ]
        for i in range(N - 1):
            k = B[i]
            if A[k - 1] == amari[0]:
                now = amari.pop(1)
            else:
                now = amari.pop(0)
            B[i + 1] = now
        print(*B)

except:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int,input().split()))

for i in range(n):
    A[i] -= 1

ANS = []
if n>3:
    ANS.append(0)
B = [0] * n
# B[0] = 1

if n==2 and A==[1,0]:
    print(-1)
elif n==2:
    print("1 2")
else:

    a = 1
    b = 2
    while len(ANS) < n-3:
        if A[ANS[-1]] != a:
            ANS.append(a)

            a = b
        elif A[ANS[-1]] != b:
            ANS.append(b)
        b += 1
    # print([i+1 for i in ANS])

    for i in range(len(ANS)):
        B[ANS[i]] += 1
    N = []
    for i in range(len(B)):
        if B[i] == 0:
            N.append(i)
    N.sort()

    # print(N)

    M = [[N[0],N[1],N[2]],[N[0],N[2],N[1]],[N[1],N[0],N[2]],\
    [N[1],N[2],N[0]],[N[2],N[0],N[1]],[N[2],N[1],N[0]]]

    for i in range(6):
        if (n<=3 or A[ANS[-1]] != M[i][0]) and A[M[i][0]] != M[i][1]\
            and A[M[i][1]] != M[i][2]:
            ANS+=M[i]
            break

    AA = [str(i+1) for i in ANS]

    print(" ".join(AA))

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
A=list(map(int,input().split()))
l=deque([i for i in range(2,n+1)])
ans=[1]
for i in range(n-1):
    a=l.popleft()
    if a==A[ans[i]-1]:
        if l:
            b=l.popleft()
            ans.append(b)
            l.appendleft(a)
        else:
            c=A[a-1]
            for j in range(n-2):
                if c!=ans[-j-1] and A[ans[-j-2]-1]!=a:
                    ans=ans[:-j-1]+[a]+ans[-j-1:]
                    print(ans)
                    exit()
            if c!=ans[0]:
                ans=[a]+ans
                print(ans)
                exit()
            else:
                print(-1)     
                exit()
    else:
        ans.append(a)
print(*ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop
import sys
import itertools
 
N=int(input())
A=[0]+list(map(int,input().split()))
if N==2:
    print(-1)
    sys.exit()
if N==3:
    for u in itertools.permutations(range(1,4)): 
        for i in range(2):
            if A[u[i]]!=u[i+1]:
                continue
            else:
                break
        else:
            print(*u)
            sys.exit()
    else:
        print(-1)
        sys.exit()
B=[[] for i in range(N+1)]
for i in range(1,N+1):
    B[A[i]].append(i)
ans=[1]
lsls=[i for i in range(2,N+1)]
for i in range(N-2):
    u=heappop(lsls)
    if A[ans[-1]]!=u:
        ans.append(u)
    else:
        ans.append(heappop(lsls))
        heappush(lsls,u)
u=lsls[0]
if A[ans[-1]]!=u:
    ans.append(u)
else:
    for i in range(N-2,-1,-1):
        if A[ans[i]]!=u:
            ans=ans[:i+1]+[u]+ans[i+1:]
            break
    else:
        ans=[u]
        lsls=[i for i in range(1,u)]+[i for i in range(u+1,N+1)]
        for i in range(N-2):
            u=heappop(lsls)
            if A[ans[-1]]!=u:
                ans.append(u)
            else:
                ans.append(heappop(lsls))
                heappush(lsls,u)
        u=lsls[0]
        ans.append(u)
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())

a = list(map(int,input().split()))

A = []

for i in range(N):
    A.append([a[i],i+1])

flag = True



for i in range(N+1):

    if i == N:
        print (-1)
        sys.exit()

    nflag = True
    for i in range(N-2):

        if A[i][0] == A[i+1][1]:
            t = A[i+2]
            A[i+2] = A[i+1]
            A[i+1] = t
            nflag = False
        elif A[i+2][1] != A[i][0] and A[i+2][1] < A[i+1][1]:
            t = A[i+2]
            A[i+2] = A[i+1]
            A[i+1] = t
            nflag = False
            
    if A[-1][1] == A[-2][0]:

        flag = False
        nflag = False
        for j in range(N-1):
            j = N-2-j

            if A[j][0] != A[-1][1]:
                A.insert(j+1,A[-1])
                del A[-1]
                flag = True
                break
        if not flag:
            A.insert(0,A[-1])
            del A[-1]

    if nflag:
        break


ans = []
for i in range(N):
    ans.append(A[i][1])

print (" ".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop
import sys
import itertools
 
N=int(input())
A=[0]+list(map(int,input().split()))
if N==2:
    print(-1)
    sys.exit()
B=[[] for i in range(N+1)]
for i in range(1,N+1):
    B[A[i]].append(i)
ans=[1]
lsls=[i for i in range(2,N+1)]
for i in range(N-2):
    u=heappop(lsls)
    if A[ans[-1]]!=u:
        ans.append(u)
    else:
        ans.append(heappop(lsls))
        heappush(lsls,u)
u=lsls[0]
if A[ans[-1]]!=u:
    ans.append(u)
else:
    for i in range(N-2,-1,-1):
        if A[ans[i]]!=u:
            ans=ans[:i+1]+[u]+ans[i+1:]
            break
    else:
        ans=[u]
        lsls=[i for i in range(1,u)]+[i for i in range(u+1,N+1)]
        for i in range(N-2):
            u=heappop(lsls)
            if A[ans[-1]]!=u:
                ans.append(u)
            else:
                ans.append(heappop(lsls))
                heappush(lsls,u)
        u=lsls[0]
        ans.append(u)
print(*ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [1 for i in range(N)]
amari = [i for i in range(2, N+1)]
try:
    for i in range(N-1):
        k = B[i]
        if A[k-1] == amari[0]:
            now = amari.pop(1)
        else:
            now = amari.pop(0)
        B[i+1] = now
    print(*B)
except:
    print(-1)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop
import sys
import itertools
 
N=int(input())
A=[0]+list(map(int,input().split()))
if N==2:
    print(-1)
    sys.exit()
B=[[] for i in range(N+1)]
for i in range(1,N+1):
    B[A[i]].append(i)
ans=[1]
lsls=[i for i in range(2,N+1)]
for i in range(N-2):
    u=heappop(lsls)
    if A[ans[-1]]!=u:
        ans.append(u)
    else:
        ans.append(heappop(lsls))
        heappush(lsls,u)
u=lsls[0]
if A[ans[-1]]!=u:
    ans.append(u)
else:
    for i in range(N-3,-1,-1):
        if A[ans[i]]!=u:
            ans=ans[:i+1]+[u]+ans[i+1:]
            break
    else:
        ans=[u]
        lsls=[i for i in range(1,u)]+[i for i in range(u+1,N+1)]
        for i in range(N-2):
            u=heappop(lsls)
            if A[ans[-1]]!=u:
                ans.append(u)
            else:
                ans.append(heappop(lsls))
                heappush(lsls,u)
        u=lsls[0]
        ans.append(u)
print(*ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True

ans=0


n=I()
a=LI()
ng=[[] for i in range(n)]

q=[1]
r=list(range(-n,-1))
heapify(r)

try:
    for i in range(n-1):
        if r:
            0
        else:
            break
        nx=-r[-1]
        #show(nx,q[-1],q,r)
        if a[q[-1]-1]==nx:
            forb=-r.pop()
            cand=-r.pop()
            q.append(cand)
            heappush(r,-forb)
        else:
            q.append(-r.pop())
except:
    print(-1)
    exit()
    
print(*q)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True

ans=0


n=I()
a=LI()
ng=[[] for i in range(n)]

q=[1]
r=list(range(-n,-1))
heapify(r)


for i in range(n-1):
    if r:
        0
    else:
        break
    nx=-r[-1]
    #show(nx,q[-1],q,r)
    if a[q[-1]-1]==nx:
        forb=-r.pop()
        try:
            cand=-r.pop()
        except:
            print(-1)
            exit()

        q.append(cand)
        heappush(r,-forb)
    else:
        q.append(-r.pop())
    
print(*q)
for i in range(n):
    ng[i].append(a[i])

Submission status: Wrong Answer

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

import itertools
import sys

n = int(input())
x = list(map(int,input().split()))
a = [i for i in range(1,n+1)]

count = 0
flag = False
ok = []

def resultPrint(ok):
    res = ""
    for i in ok:
        if res == "":
            res = str(i)
        else:
            res += " " + str(i)
    print(res)
    sys.exit()

for i in itertools.permutations(a):
    for j in range(len(i)-1):
        if x[count] == i[count + 1]:
            flag = True
            break
        count += 1
    if flag == False:
        ok = i
        break
    else:
        flag = False
        count = 0

if ok != []:
    resultPrint(ok)
else:
    print("-1")

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
x = list(map(int,input().split()))

d = [0]*(N-1)
for i in range(N-1):
    d[i] = x[i+1]-x[i]
    d[i] %= 10**9+7


kaijou = 1
for i in range(1,N):
    kaijou *= i%(10**9+7)

kaijou = math.factorial(N-1)%(10**9+7)
ans=0
x=0
k=10**9+5

def pow_r(x, n):
    """
    O(log n)
    """
    x %= (k+2)
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r(x ** 2, n // 2)%(k+2)
    else:  # standard case ② n is odd
        return (x * pow_r(x ** 2, (n - 1) // 2))%(k+2)

for i in range(N-1):
    #(i+1)**(10**9+5)を計算してyへ
    y = pow_r(i+1,k) 
    #x+= kaijou//(i+1))%(10**9+7)
    x += (kaijou*y)%(10**9+7)
    ans+= d[i]*x

print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop
import sys
import itertools
 
N=int(input())
A=[0]+list(map(int,input().split()))
if N==2:
    print(-1)
    sys.exit()
if N==3:
    for u in itertools.permutations(range(1,4)): 
        for i in range(2):
            if A[u[i]]!=u[i+1]:
                continue
            else:
                break
        else:
            print(*u)
            sys.exit()
    else:
        print(-1)
        sys.exit()
B=[[] for i in range(N+1)]
for i in range(1,N+1):
    B[A[i]].append(i)
ans=[1]
lsls=[i for i in range(2,N+1)]
for i in range(N-2):
    u=heappop(lsls)
    if A[ans[-1]]!=u:
        ans.append(u)
    else:
        ans.append(heappop(lsls))
        heappush(lsls,u)
u=lsls[0]
if A[ans[-1]]!=u:
    ans.append(u)
else:
    for i in range(N-3,-1,-1):
        if A[ans[i]]!=u:
            ans=ans[:i+1]+[u]+ans[i+1:]
            break
    else:
        ans=[u]
        lsls=[i for i in range(1,u)]+[i for i in range(u+1,N+1)]
        for i in range(N-2):
            u=heappop(lsls)
            if A[ans[-1]]!=u:
                ans.append(u)
            else:
                ans.append(heappop(lsls))
                heappush(lsls,u)
        u=lsls[0]
        ans.append(u)
print(*ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True

ans=0


n=I()
a=LI()
ng=[[] for i in range(n)]

q=[1]
r=list(range(-n,-1))
heapify(r)

try:
    for i in range(n-1):
        if r:
            0
        else:
            break
        nx=-r[-1]
        #show(nx,q[-1],q,r)
        if a[q[-1]-1]==nx:
            forb=-r.pop()
            cand=-r.pop()
            q.append(cand)
            heappush(r,-forb)
        else:
            q.append(-r.pop())
except:
    print(-1)
    exit()
    
print(*q)
for i in range(n):
    ng[i].append(a[i])

show(a)
show(ng)

Submission status: Wrong Answer

Solution code:
import heapq
N = int(input())
A = list(map(int,input().split()))
def solve(x,flag):
    a,b = [i+1 for i in range(N)],0
    a[x-1] = 10**9+7
    ans = [x]
    taboo = A[x-1]
    heapq.heapify(a)
    ans0 = ""
    for i in range(N-1):
        p = heapq.heappop(a)
        if taboo == p:
            b = p
            p = heapq.heappop(a)
        ans.append(p)
        if p >= N+10:
            if flag:
                flag = False
                return solve(b,False)
            else:
                return [-1]
        taboo = A[p-1]
        if b:
            heapq.heappush(a,b)
            b = 0
    return ans
print(*solve(1,True))

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())

a = list(map(int,input().split()))

A = []

for i in range(N):
    A.append([a[i],i+1])

flag = True



for i in range(N+1):

    if i == N:
        print (-1)
        sys.exit()

    nflag = True
    for i in range(N-2):

        if A[i][0] == A[i+1][1]:
            t = A[i+2]
            A[i+2] = A[i+1]
            A[i+1] = t
            nflag = False

    if A[-1][1] == A[-2][0]:

        flag = False
        nflag = False
        for j in range(N-1):
            j = N-2-j

            if A[j][0] != A[-1][1]:
                A.insert(j+1,A[-1])
                del A[-1]
                flag = True
                break
        if not flag:
            A.insert(0,A[-1])
            del A[-1]

    if nflag:
        break


ans = []
for i in range(N):
    ans.append(A[i][1])

print (" ".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())

a = list(map(int,input().split()))

A = []

for i in range(N):
    A.append([a[i],i+1])

flag = True



for i in range(N+1):

    if i == N:
        print (-1)
        sys.exit()

    nflag = True
    for i in range(N-2):

        if A[i][0] == A[i+1][1]:
            t = A[i+2]
            A[i+2] = A[i+1]
            A[i+1] = t
            nflag = False

    if A[-1][1] == A[-2][0]:

        flag = False
        nflag = False
        for j in range(N-1):
            j = N-2-j

            if A[j][0] != A[-1][1] and A[j+1][1] != A[-1][0]:
                A.insert(j+1,A[-1])
                del A[-1]
                flag = True
                break
        if not flag:
            A.insert(0,A[-1])
            del A[-1]

    if nflag:
        break


ans = []
for i in range(N):
    ans.append(A[i][1])

print (" ".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
import itertools
from copy import deepcopy
import heapq
import numpy as np
n=int(input())
List=list(map(int,input().split()))
# npli=np.array(List)
listcp=deepcopy(List)
List=list(range(1,n+1))
heapq.heapify(List)
# npli=np.sort(npli)
ans=[heapq.heappop(List)]
for i in range(1,n):
    a=heapq.heappop(List)
    if(i==n-1):
        ans.append(a)
        break
    if(a==listcp[ans[i-1]-1]):
        ans.append(heapq.heappop(List))
        heapq.heappush(List, a)
    else:
        ans.append(a)
# ans.append(heapq.heappop(List))
if(n==2):
    if(ans[0]==listcp[1]):
        print(-1)
        exit(0)
if(len(ans)!=n):
    # print(" ".join(ans))
    print(-1)
else:
    print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush


def solve(n, a_list):
    h = []
    for i in range(1, n + 1):
        heappush(h, i)
    res_list = []
    forbidden_list = []
    forbid = 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[-1]
                if a_list[j - 1] == i:
                    heappush(h, res_list.pop())
                else:
                    res_list.append(i)
                    break
            if len(res_list) == 0:
                # print(i, h)
                forbid = a_list[i - 1]
                res_list.append(i)
                forbidden_list.append(i)
                if len(forbidden_list) == n:
                    return "-1"
    # print(res_list, forbidden_list)
    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: Wrong Answer

Solution code:
from heapq import heappush,heappop
import sys
N=int(input())
A=[0]+list(map(int,input().split()))
B=[[] for i in range(N+1)]
for i in range(1,N+1):
    B[A[i]].append(i)
ans=[1]
lsls=[i for i in range(2,N+1)]
for i in range(N-2):
    u=heappop(lsls)
    if A[ans[-1]]!=u:
        ans.append(u)
    else:
        ans.append(heappop(lsls))
        heappush(lsls,u)
u=lsls[0]
if A[ans[-1]]!=u:
    ans.append(u)
else:
    for i in range(N-3,-1,-1):
        if A[ans[i]]!=u:
            ans=ans[:i+1]+[u]+ans[i+1:]
            break
    else:
        print(-1)
        sys.exit()
print(*ans)

Submission status: Wrong Answer

Solution code:
import heapq
N = int(input())
A = list(map(int,input().split()))
a,b = [i+1 for i in range(N)],0
a.append(10**9+7)
ans = []
taboo = -1
if max(A) == min(A):
    ans.append(max(A))
    a[max(A)-1] = 10**9+7
    N -= 1
heapq.heapify(a)

for i in range(N):
    p = heapq.heappop(a)
    if taboo == p:
        b = p
        p = heapq.heappop(a)
    ans.append(p)
    if p >= N+10:
        print(-1)
        exit()
    if p >= N+10:
        print(-1)
        exit()
    taboo = A[p-1]
    if b:
        heapq.heappush(a,b)
        b = 0


print(*ans)