[PYTHON] Atcoder Begginer Contst 065 --B: formé?

Atcoder Begginer Contst 065 -- B: Trained? https://atcoder.jp/contests/abc065 Les deux codes suivants sont tous identiques à l'exception du nombre de variables. C'était version1 => AC, version2 => TLE. Il y a une différence entre bool et int, donc je ne peux pas blâmer l'ajout, mais je ne pensais pas que cela ferait autant de différence que TLE ...

version1.py

N = int(input())
A = []
for i in range(N):
  A.append(int(input())-1)
    
ans = -1
push = 0
count = [False]*N
for i in range(N+1):
 
    if A[push] == 1:
        ans = i+1
        break
        
    elif count[push]:
      break
      
    else:
        count[push] = True
        push = A[push] 
      
print(ans)

version2.py

N = int(input())
A = []
for i in range(N):
  A.append(int(input())-1)
    
ans = -1
push = 0
count = []
for i in range(N+1):
 
    if A[push] == 1:
        ans = i+1
        break
        
    elif A[push] in count:
      break
      
    else:
      count.append(push)
      push = A[push]
        
print(ans)

Ou la 15e ligne de la version 2

elif A[push] in count:
    break

Peut-être lent ...? Vous devez être prudent lors de la manipulation de la liste Ikansen ... Si quelqu'un connaît la cause, veuillez commenter.

Postscript

J'ai changé la variable de compte de la liste à l'ensemble et ce n'est plus des TLE. Après tout, je pense que xx dans la liste était lent.

Conclusion: utilisez xx dans l'ensemble au lieu de xx dans la liste.

version3.py

N = int(input())
A = []
for i in range(N):
  A.append(int(input())-1)
    
ans = -1
push = 0
count = set()
 
for i in range(N+1):
 
    if A[push] == 1:
        ans = i+1
        break
        
    elif A[push] in count:
      break
      
    else:
      count.add(push)
      push = A[push]
        
print(ans)