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: 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
        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[-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
                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)

        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
        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[-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
                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)

        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
        c1 += 1
        if c1 > 2 * n:
            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
    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]
                    h = []
                    break
    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
    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]
                    h = []
                    break
    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:
import collections
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        a = list(map(int, input().split()))

        next_cards = {}
        for i in range(N):
            a_i = a[i]
            _min = min(i + 1, a_i)
            _max = max(i + 1, a_i)
            next_cards[i + 1] = list(range(1, _min)) + list(range(_min + 1, _max)) + list(range(_max + 1, N + 1))

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

        ans = []
        while deq:
            card, cards = deq.popleft()
            cards_set = set(cards)
            for next_card in next_cards[card][::-1]:
                if next_card not in cards_set:
                    if len(cards) == N - 1:
                        ans = cards + [next_card]
                        break
                    deq.appendleft((next_card, cards + [next_card]))
            if ans:
                break

        if ans:
            print(*ans)
        else:
            print(-1)


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

def judge(lst,rules):
    for i in range(len(lst)):
        if i == len(lst)-1:
            return True
        if lst[i + 1] == rules[lst[i]]:
            return False
    return True


def main():
    n = int(input())
    cards = [x for x in range(1,n+1)]
    rule_nums = list(map(int,input().split()))
    rules = dict()
    for i in range(n):
        rules[i+1] = rule_nums[i]

    answer = -1

    for pattern in permutations(cards):
        if judge(pattern,rules):
            answer = " ".join(map(str,pattern))
            break
    print(answer)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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)
                    forbid = a_list[i - 1]
                    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: Time Limit Exceeded

Solution code:
import collections
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        a = list(map(int, input().split()))

        next_cards = {}
        for i in range(N):
            a_i = a[i]
            _min = min(i + 1, a_i)
            _max = max(i + 1, a_i)
            next_cards[i + 1] = list(range(1, _min)) + list(range(_min + 1, _max)) + list(range(_max + 1, N + 1))

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

        ans = []
        while deq:
            card, cards = deq.popleft()
            if len(cards) == N:
                ans = cards
                break
            for next_card in next_cards[card][::-1]:
                if next_card not in cards:
                    deq.appendleft((next_card, cards + [next_card]))

        if ans:
            print(*ans)
        else:
            print(-1)


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-



n = int(input())
a = input().split()
dict_set = {}
for i in range(1, n + 1):
    dict_set[str(i)] = a[i-1]

def func(suuzi, check_list):
    if len(check_list) == n:
        ans = " ".join(check_list)
        return 1, ans
    else:
        for i in range(1, n + 1):
            if str(i) in check_list or dict_set[suuzi] == str(i):
                continue
            flag, ans = func(str(i), check_list + [str(i)])
            if flag == 1:
                return 1, ans
        return 0, "-1"

for i in range(1, n + 1):
    check_list = [str(i)]
    flag, ans = func(str(i), check_list)
    if flag == 1:
        break
print(ans)

Submission status: Accepted

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_d
左からおいていくことを考える
残ったカード全てから嫌われている場合、もう置くしかない
貪欲に置いていき、残りカード全てから嫌われてしまったら置く？

そうなるとただの実装難問題だが…

for i in range(N)
    if 残りのカード全てから嫌われてしまっているカードがあったら置く。
    elif 辞書順最小のカードが置けたら置く
    elif 辞書順2番目のカードが存在したら置く。
    else -1?

なのか？？
3枚以上なら絶対置くことが可能そうに見える


残りのカード全てから嫌われてしまっている、判定はどうすればよいと？
嫌われてる辞書(残存するカードのみ)を作っておき、len(辞書) == 2 で、1でない方が嫌われ者

elif 以降はheapqを使うのが良さそう
おいてるフラグ配列を管理しておき、置いてないが出るまでpop
置けない場合は、もう1つ出るまでpopし、置いて最初の奴を戻す

何が問題なんだ…？
この方法だとqueueが空になってしまうけど構成不可能ではない、ケースが存在する
N==2で-1は正しかった
互いに嫌いな2個が最後に残るとまずい
→最後の3つを全探索するか？
→これが丸そう
"""

def allserch(dnt,x,y,z):

    ret = []
    if dnt != x and a[x] != y and a[y] != z:
        ret.append([x,y,z])
    if dnt != x and a[x] != z and a[z] != y:
        ret.append([x,z,y])
    if dnt != y and a[y] != x and a[x] != z:
        ret.append([y,x,z])
    if dnt != y and a[y] != z and a[z] != x:
        ret.append([y,z,x])
    if dnt != z and a[z] != x and a[x] != y:
        ret.append([z,x,y])
    if dnt != z and a[z] != y and a[y] != x:
        ret.append([z,y,x])
    ret.sort()
    return ret[0]


import heapq
import sys

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

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

for i in range(N):
    a[i] -= 1

ans = []
dont = None

hq = []
for i in range(N):
    heapq.heappush(hq,i)
    
usable = [True] * N
dic = {}
for i in range(N):
    if a[i] not in dic:
        dic[a[i]] = 1
    else:
        dic[a[i]] += 1


for loop in range(N-3):

    flag = True
    
    if len(dic) == 2:
        maxind = None

        for i in dic:
            if maxind == None:
                maxind = i
            elif dic[i] > dic[maxind]:
                maxind = i

        if dic[maxind] == (N-loop-1) and usable[maxind]:
            nc = maxind
            flag = False

    if flag:

        while (not usable[hq[0]]):
            heapq.heappop(hq)
            
        fi = heapq.heappop(hq)
        if dont != fi:
            nc = fi
        else:

            while (not usable[hq[0]]):
                heapq.heappop(hq)

            
            sec = heapq.heappop(hq)
            heapq.heappush(hq,fi)
            nc = sec

    #print (nc,a[nc])
    ans.append(nc+1)
    usable[nc] = False
    dic[a[nc]] -= 1
    dont = a[nc]
    if dic[a[nc]] == 0:
        del dic[a[nc]]

pas = []
while len(hq) > 0:
    now = heapq.heappop(hq)
    if usable[now]:
        pas.append(now)

rec = allserch(dont,pas[0],pas[1],pas[2])
for i in range(3):
    rec[i] += 1
ans += rec

print (*ans)

Submission status: Accepted

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 = 10 ** 20
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[0] == 2 and A[1] == 1:
        print(-1)
    elif A[0] != 2:
        print(1, 2)
    else:
        print(2, 1)
    exit()


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


ans = []
pre = -1
for j in range(n - 1):
    x = bit.search(1)
    if x == pre:
        x = bit.search(2)
    bit.add(x, -1)
    ans += [x]
    pre = A[x - 1]

last_x = bit.search(1)
bit.add(last_x, -1)
if A[ans[-1] - 1] != last_x:
    ans += [last_x]
    print(*ans)
    exit()


cnt = 0
for k in range(n - 2, -1, -1):
    if A[ans[k] - 1] == last_x:
        x = ans.pop()
        bit.add(x, 1)
        cnt += 1
    else:
        break


if cnt == 1:
    last3 = []
    for a, b, c in permutations((ans.pop(), x, last_x)):
        if A[ans[-1] - 1] != a and A[a - 1] != b and A[b - 1] != c:
            last3 += [[a, b, c]]
    print(*ans + min(last3))
    exit()


ans += [last_x]
x = bit.search(1)
if x == A[ans[-1] - 1]:
    x = bit.search(2)
bit.add(x, -1)
ans += [x]
for l in range(cnt - 1):
    x = bit.search(1)
    bit.add(x, -1)
    ans += [x]
print(*ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from heapq import heappop, heappush
from itertools import permutations
from operator import itemgetter


# ある条件に当てはまらない限り、i番目に置く数字 xi は、
# それまで使ってない中で最も小さい数字か、
# またはその次に小さい数字（x[i-1]の右に最も小さい数字を置けない場合）
#
# ある条件: 以下の条件を満たす、未使用の数 k がある
# 残っているk以外の全ての数字が、kを共通して右側に置けない数として指定している
#   ＝kを先頭に持ってこない限り、kを置ける機会が無い
#
# ただし残りが少なく（3以下）なってくると例外的なものが出てくるため、それ以降は全探索

def fill_remainings(ans, aaa, x, remainings):
    """
    xを先頭にして残りを昇順に追加
    ただしxの次の要素のみ、aaa[x]で禁止されていた場合はその次と入れ替える
    remainingsにはxを含め3要素以上残っていることが前提
    """
    ans.append(x)
    i = len(ans)
    while remainings:
        k = heappop(remainings)
        if k != x:
            ans.append(k)
    if aaa[x] == ans[i]:
        ans[i], ans[i + 1] = ans[i + 1], ans[i]


def solve(n, aaa):
    if n == 2:
        return [-1]

    in_degrees = defaultdict(lambda: 0)
    for i, a in enumerate(aaa, start=1):
        in_degrees[a] += 1
    in_degrees = dict(in_degrees)

    # 少なくとも残り個数がこれ+1になるまでは「ある条件」には当てはまらない
    # ただし減少することはあるため、直前に再チェック必要
    curr_max = max(in_degrees.values())

    remainings = list(range(1, n + 1))

    aaa.insert(0, 0)

    ans = []
    banned = -1
    for i in range(n - 3):
        if curr_max == n - i - 1:
            curr_x, curr_max = max(in_degrees.items(), key=itemgetter(1))
            if curr_max == n - i - 1:
                fill_remainings(ans, aaa, curr_x, remainings)
                return ans
        top = heappop(remainings)
        if top == banned:
            ans.append(heappop(remainings))
            heappush(remainings, top)
        else:
            ans.append(top)
        banned = aaa[ans[-1]]
        # 確定した数字の入り次数を削減
        if banned in in_degrees:
            if in_degrees[banned] == 1:
                del in_degrees[banned]
            else:
                in_degrees[banned] -= 1
        in_degrees.pop(ans[-1], 0)

    remainings.sort()
    for i, j, k in permutations(remainings):
        if i != banned and j != aaa[i] and k != aaa[j]:
            ans += [i, j, k]
            break

    return ans


n, *aaa = map(int, sys.stdin.buffer.read().split())
print(*solve(n, aaa))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N=int(input())
A=[0]+list(map(int,input().split()))

if N==2 and A==[0,2,1]:
    print(-1)
    sys.exit()


C=[0]*(N+1)

for i in range(1,N+1):
    if A[i]!=i:
        C[A[i]]+=1

import heapq

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

heapq.heapify(H)
NOUSE=list(range(N,0,-1))
USELIST=[0]*(N+1)
ANS=[0]

for rest in range(N-1,2,-1):
    #print(ANS,NOUSE,H,rest)
    
    if -H[0][0]==rest and rest!=0:
        x,y=heapq.heappop(H)
        ANS.append(y)
        C[y]=0
        C[A[y]]-=1
        USELIST[y]=1

    else:
        for i in range(len(NOUSE)-1,-1,-1):
            if USELIST[NOUSE[i]]==0 and A[ANS[-1]]!=NOUSE[i]:
                x=NOUSE.pop(i)
                ANS.append(x)
                USELIST[x]=1
                C[x]=0
                C[A[x]]-=1
                break
            

    while C[H[0][1]]!=-H[0][0]:
        x,y=heapq.heappop(H)
        heapq.heappush(H,(-C[y],y))

    while NOUSE and USELIST[NOUSE[-1]]==1:
        NOUSE.pop()


NOUSE=[i for i in range(N+1) if USELIST[i]==0]

from itertools import permutations
REST=list(permutations(sorted(NOUSE[1:])))

if len(REST)==2:
    for x,y in REST:
        if A[ANS[-1]]!=x and A[x]!=y:
            ANS.extend([x,y])
            break

else:    
    for x,y,z in REST:
        if A[ANS[-1]]!=x and A[x]!=y and A[y]!=z:
            ANS.extend([x,y,z])
            break

print(*ANS[1:])

Submission status: Accepted

Solution code:
from itertools import permutations
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

# smallで作った数列のチェック
def check_s(res, ngi):
    if res[0] == ngi: return False
    for i in range(len(res) - 1):
        if res[i + 1] == ng[res[i]]:
            return False
    return True

# nが小さいときの全探索用
def small(remain, ngi):
    for res in permutations(remain):
        if check_s(res, ngi): return res
    return [-2]

# 使った数を消しながら最小の数を返す
def delpop():
    while 1:
        i = heappop(hp)
        if not used[i]: return i

# 次の数を選ぶ
def next_i(ngi, cr):
    i = delpop()
    if i == ngi:
        ii = delpop()
        heappush(hp, i)
        i = ii
    ngj = ng[i]
    if used[ngj]: return i
    if indeg[ngj] < cr - 1: return i
    heappush(hp, i)
    return ngj

def main():
    # 頂点iを追加しても、残りの頂点でハミルトンパスが存在するかチェックしながら
    # 残りが4点になるまで小さい順に頂点を選んでいく
    ans = []
    ngi = -1
    cnt_remain = n
    for _ in range(n - 4):
        i = next_i(ngi, cnt_remain)
        ans.append(i)
        used[i] = True
        cnt_remain -= 1
        ngi = ng[i]
        indeg[ngi] -= 1
    # 4点以下の残りについては愚直に探す
    remain = []
    while hp:
        i=heappop(hp)
        if used[i]:continue
        remain.append(i)
    ans += small(remain, ngi)
    ans = [x + 1 for x in ans]
    print(*ans)

n = II()
ng = LI1()
hp = list(range(n))
heapify(hp)
used = [False] * n
indeg = [0] * n
for k in ng: indeg[k] += 1
main()