Résolvez ABC167-D avec Python

introduction

Résolvez D qui n'a pas pu être résolu hier

** Pensées ** Puisque $ K $ est gros, il semble qu'il ne peut être résolu que s'il est bouclé quelque part → Détectons la boucle. Et il sera classé selon la taille de $ K $. Tout ce que vous devez mettre en œuvre est une liste pour déterminer si vous êtes en visite et une liste pour enregistrer l'ordre des visites. La première liste empêche les boucles infinies et la dernière liste facilite la mise en œuvre ultérieure.

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

s = [True] * n #Liste pour déterminer si vous visitez
c = [1] #Liste pour enregistrer l'ordre des visites
now = 0 #Localisation actuelle
while s[now]:
    s[now] = False #Enregistrez les points que vous avez visités
    now = a[now] - 1
    c.append(now+1)

start_cycle = c.index(c[-1]) #Pointez pour entrer dans la boucle
loop = c[start_cycle:-1] #Liste des boucles
cycle = len(loop)

if k < start_cycle: #K incapable d'atteindre la boucle
    print(c[k])
else:
    k -= start_cycle
    k %= cycle
    print(loop[k])

Résumé

Si j'étais calme, j'étais déçu car j'ai pu le résoudre pendant le concours. à plus.