241502026-02-04 23:21:2442Ültetéspypy3Accepted 75/7596ms24492 KiB
from sys import stdin
input=stdin.readline

def solv():
    N = int(input())
    graph = [0]+list(map(int,input().split()))
    ginv = [[] for i in range(N+1)]
    for i in range(1,N+1):
        ginv[graph[i]].append(i)
    ord=sorted(range(1,N+1),key=lambda x: len(ginv[x]))
    visited = {ord[0]}
    cur=[ord[0]]
    while graph[cur[-1]] not in visited:
        visited.add(graph[cur[-1]])
        cur.append(graph[cur[-1]])
    if len(cur) == N:
        print(N-1)
        rr=[0]*N
        for i in range(N):
            rr[cur[i]-1]=i+1
        print(*rr)
        return
    tmp = [cur[0]]
    while ginv[tmp[-1]] and ginv[tmp[-1]][-1] not in visited:
        tmp.append(ginv[tmp[-1]].pop())
        visited.add(tmp[-1])
    res=tmp[:0:-1]+cur
    r=len(res)-1
    for start in ord:
        if start in visited:
            continue
        visited.add(start)
        cur=[start]
        while graph[cur[-1]] not in visited:
            visited.add(graph[cur[-1]])
            cur.append(graph[cur[-1]])
        tmp = [cur[0]]
        while ginv[tmp[-1]] and ginv[tmp[-1]][-1] not in visited:
            tmp.append(ginv[tmp[-1]].pop())
            visited.add(tmp[-1])
        RES=tmp[:0:-1]+cur
        r+=len(RES)-1
        res += RES
    print(r)
    rr=[0]*N
    for i in range(N):
        rr[res[i]-1]=i+1
    print(*rr)

solv()
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted43ms19688 KiB
2Accepted79ms23724 KiB
subtask25/5
3Accepted39ms19712 KiB
4Accepted43ms19848 KiB
5Accepted39ms19632 KiB
6Accepted43ms19640 KiB
7Accepted39ms19712 KiB
subtask35/5
8Accepted39ms19920 KiB
9Accepted39ms19648 KiB
10Accepted46ms19652 KiB
11Accepted43ms19684 KiB
12Accepted39ms19888 KiB
subtask45/5
13Accepted39ms19776 KiB
14Accepted48ms21080 KiB
15Accepted48ms21176 KiB
16Accepted43ms21444 KiB
17Accepted48ms21224 KiB
subtask510/10
18Accepted43ms21064 KiB
19Accepted56ms21436 KiB
20Accepted57ms21416 KiB
21Accepted50ms21532 KiB
22Accepted61ms21480 KiB
23Accepted41ms21084 KiB
24Accepted41ms21068 KiB
25Accepted56ms21484 KiB
26Accepted74ms24492 KiB
27Accepted67ms24300 KiB
subtask610/10
28Accepted57ms21656 KiB
29Accepted64ms22436 KiB
30Accepted64ms22440 KiB
31Accepted71ms22856 KiB
32Accepted64ms23268 KiB
33Accepted65ms23872 KiB
34Accepted76ms23892 KiB
35Accepted74ms24308 KiB
36Accepted65ms24220 KiB
37Accepted76ms24264 KiB
subtask740/40
38Accepted50ms21480 KiB
39Accepted78ms23216 KiB
40Accepted75ms22924 KiB
41Accepted82ms23220 KiB
42Accepted75ms23184 KiB
43Accepted93ms23748 KiB
44Accepted90ms24284 KiB
45Accepted79ms24292 KiB
46Accepted79ms24296 KiB
47Accepted90ms23956 KiB
48Accepted89ms24036 KiB
49Accepted79ms24044 KiB
50Accepted93ms24380 KiB
51Accepted86ms24248 KiB
52Accepted89ms23924 KiB
53Accepted79ms24084 KiB
54Accepted93ms24296 KiB
55Accepted81ms23952 KiB
56Accepted82ms23956 KiB
57Accepted96ms23940 KiB