Problem:


Score: 400 points

Problem Statement

The Kingdom of Takahashi has N towns, numbered 1 through N.

There is one teleporter in each town. The teleporter in Town i (1 \leq i \leq N) sends you to Town A_i.

Takahashi, the king, loves the positive integer K. The selfish king wonders what town he will be in if he starts at Town 1 and uses a teleporter exactly K times from there.

Help the king by writing a program that answers this question.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq A_i \leq N

1 \leq K \leq 10^{18}

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the integer representing the town the king will be in if he starts at Town 1 and uses a teleporter exactly K times from there.

Sample Input 1

4 5
3 2 4 1

Sample Output 1

4

If we start at Town 1 and use the teleporter 5 times, our travel will be as follows: 1 \to 3 \to 4 \to 1 \to 3 \to 4.

Sample Input 2

6 727202214173249351
6 5 2 5 3 2

Sample Output 2

2



Sample input:
4 5
3 2 4 1


Sample output:
4

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = [0]+list(map(int,input().split()))

def bin(arr,val):
    left,right = 0,len(arr)-1
    while left<=right:
        mid = (left+right)//2
        if arr[mid]==val: return 1
        elif arr[mid]<val: left = mid + 1
        else: right = mid - 1
    return 0

know = []
now = 1
while not bin(know, now):
    know.append(now)
    now = a[now]

start = a[know[-1]]
for i,num in enumerate(know):
    if num == start: loop = know[i:] ; break

print(know,start,loop)

if k < len(know):
    ans = know[k]
else:
    k -= len(know)
    ans = loop[k%len(loop)]

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
As = list(map(int,input().split()))
As_io = [-1]+[-1]*(N-1)


to = As[0]
# print("------")
# print("1",end="->")
for i in range(K):
    # print(str(to), end="->")

    if to == As[to-1]:
        print(to)
        break
    
    elif As_io[to-1] > -1:
        # print("\n")
        # print("now loop")
        cycle = i+1-As_io[to-1]
        # print(cycle)
        remain =  (K-(i+1)) % cycle
        if remain == 0:
            print(to)
        else:
            for j in range(remain):
                to = As[to-1]
            print(to)
        break
        
    else:
        As_io[to-1] = i+1
        to = As[to-1]

Submission status: Wrong Answer

Solution code:
import numpy as np
N, K = list(map(int, input().split()))
A = np.array(list(map(int, input().split()))) - 1
mem = np.zeros((N, 2))

c = 0 # 現在の場所
cK = 0 # 現在の回数
flg = True
for k in range(1, K+1):
    c = A[c] # k回目の移動先
    mem[c][0] += 1
    if np.any(mem>1):
        T = k - mem[c][1]
        cK = k
        flg = False
        break
    mem[c][1] = k
    
if flg:
    print(c+1)
else:
    iterN = int((K - cK) % T)
    if iterN > 0:
        for i in range(iterN):
            c = A[c]
    print(c+1)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
dp = [0] * (n+1)
B = []
f = 1
c = 0
ans = n
bal = 0
while dp[f-1] == 0:
    dp[f-1] =-1
    B.append(f)
    f = A[f-1]
    c +=1

t = B.index(f)
B = B[B.index(f):]
k -= t
k%=len(B)

print(B[k])

Submission status: Wrong Answer

Solution code:
import collections
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[]
now=0
for i in range(n+1):
        ans.append(a[now])
        now=a[now]-1
#print(ans)

ans2=collections.Counter(ans)

ac=ans2.most_common()[0][0]
#print(ac)
index=-1
index2=-1

for i in range(len(ans)):
    if ans[i]==ac:
        if index==-1:        
            index=i
        else:
            index2=i
assert(index2 != -1)
#print(index,index2)
#print((k-index-1)%(index2-index))
if k < index:
    print(ans[k])
else:
    print(ans[(k-index-1)%(index2-index)+index])

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = [0]+list(map(int,input().split()))

def bin(arr,val):
    left,right = 0,len(arr)-1
    while left<=right:
        mid = (left+right)//2
        if arr[mid]==val: return 1
        elif arr[mid]<val: left = mid + 1
        else: right = mid - 1
    return 0

know = []
now = 1
while not bin(know, now):
    know.append(now)
    now = a[now]

start = a[know[-1]]
for i,num in enumerate(know):
    if num == start: loop = know[i:] ; break

#print(know,start,loop)

if k < len(know):
    ans = know[k]
else:
    k -= len(know)
    ans = know[k%len(loop)]

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
def tele(i):
    ans = A[i-1]
    return ans
i = tele(1)
if N >= K:
    for j in range(K-1):
        i = tele(i)
        print(i)
else:
    l = [i]
    for j in range(N-1):
        i = tele(i)
        if i not in l:
            l.append(i)
    else:
        a = l.index(i)
        loop = len(l) - a
        ans = (K - a) % loop
        if ans != 0:
            q = l[a + ans -1]
        else:
            q = l[a+loop-1]
        print(q)

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().strip().split()))

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

visited = [-1] * n
now = 0
visited[0] = 0
pre_roop = 0
pos = 0
i = 1
r = 1
while i <= k:
    next = a[now]
    #print('roop:',i,now+1,next+1)
    if visited[next] >= 0:
        r = i-visited[next]
        pre_roop = visited[next]
        pos = next
        #print(i,r,pre_roop,next)
        #print(visited)
        break
    else:
        visited[next] = i
        now = next
        #print(i,visited)
        i += 1

if i >= k:
    print(now + 1)
else:
    l = (k - pre_roop) % r
    #print(l)
    i = 0
    p = pos
    while i < l:
        p = a[p]
        i +=1

    print(p+1)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, K = list(map(int, input().split()))
A = np.array(list(map(int, input().split()))) - 1
mem = np.zeros((N, 2))

c = 0 # 現在の場所
cK = 0 # 現在の回数
flg = True
for k in range(1, K+1):
    c = A[c] # k回目の移動先
    mem[c][0] += 1
    if np.any(mem>1):
        T = k - mem[c][1]
        cK = k
        flg = False
        break
    mem[c][1] = k
    
if flg:
    print(c+1)
else:
    iterN = int((K - k) % T)
    if iterN > 0:
        for i in range(iterN):
            c = A[c]
    print(c+1)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))

visited = [0]*N
i = 0
rootin = [0]*N
rootin[0] = 1
count = 0
while  visited.count(2) == 0:
  count += 1
  visited[i] += 1
  if visited[i] == 2:
    end = count
    break
  rootin[count] = A[i]
  i = A[i]-1
print(A)

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
a = [0] + list(map(int, input().split()))

r = [1]
now = 1
for i in range(n):
   now = a[now]
   if now in r: break
   r.append(now)
I = r.index(now)
if I != 0: 
  k -= I
  r = r[I:]
print(r[k%(len(r))])

Submission status: Wrong Answer

Solution code:
import sys

# print('input >>')
N, K = map(int,(input().split()))
As = list(map(lambda x: int(x)-1,(input().split())))

now = 0
# move = 1
nows = [0]
p = 0

# print('-----output-----')
while True:
    # move += 1
    now = As[now]
    if now in nows:
        p = now
        rep_start = len(nows)
        nows = nows[::-1]
        move = nows.index(now)+1
        break
    nows.append(now)

now = 0
if rep_start > K:
    for i in range(K):
        now = As[now]
        print(now+1)
        sys.exit()

now = 0
for i in range(rep_start):
    now = As[now]


K -= rep_start
K %= move
now = p

for i in range(K):
    now = As[now]

print(now+1)

Submission status: Wrong Answer

Solution code:
# = int(input())
N, K = map(int, input().split())
A = list(map(int, input().split()))
# = [int(input()) for i in range(N)]
# = [list(map(int, input().split())) for i in range(N)]
next = 1
List = [-1]*N

for i in range(K):
    if List[next-1] == -1:
        List[next-1] = i
        next = A[next-1]

    else:
        loop = i - List[next-1]
        afterloop = (K-(i-loop))%loop
        print(A[i - loop + afterloop])
        exit()

print(next)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[int(i)-1 for i in input().split()]
ed=[False]*n
go=0
c=0
cc=0
while not ed[go]:
    ed[go]=True
    go=a[go]
    c+=1
goed=a[go]
ed=[False]*n
while not ed[go]:
    ed[go]=True
    go=a[go]
    cc+=1

for i in range((k-c)%cc):
    go=a[go]
print(go+1)

Submission status: Wrong Answer

Solution code:
def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    l = [0]
    for i in range(15):
        b = a[l[i]]-1
        l.append(b)
        if l.count(b) == 2:
            break
    
    for i in range(len(l)):
        if l[i] == l[-1]:
            loop = l[i:len(l)+1]
            break

    k -= (len(l)-1) - (len(loop)-1)
    ind = loop[k%len(loop)-1]
    
    return ind+1


print(solve())

Submission status: Wrong Answer

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

li = [-1] * n
li[0] = 0
town = [0]
now = 0
flag = False

for i in range(k):
    now = a[now] - 1
    if li[now] != -1:
        s = li[now]
        break
    else:
        li[now] = i + 1
        town.append(now)
    if i == k-1:
        flag = True

if flag:
    print(town[-1])
    exit()

town2 = town[s:]
m = len(town2)
l = len(town) - len(town2)

print(town2[(k - l) % m]+1)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))

C=[1]
D=[0 for i in range(N)]
p=0
q=0

check=set(i+2 for i in range(N-1))

for i in range(N):
    C.append(A[C[i]-1])
    p+=1
    for j in check:
        D[j-1]+=1
    if not C[i+1] in check:
        q=C[i+1]
        break
    check.remove(C[i+1])

print(C[K%(p-D[q-1])])

Submission status: Wrong Answer

Solution code:
import collections
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[]
now=0
for i in range(n+1):
        ans.append(a[now])
        now=a[now]-1
#print(ans)

ans2=collections.Counter(ans)

ac=ans2.most_common()[0][0]
#print(ac)
index=-1
index2=-1

for i in range(len(ans)):
    if ans[i]==ac:
        if index==-1:        
            index=i
        else:
            index2=i

#print(index,index2)
#print((k-index-1)%(index2-index))
if k < index:
    print(ans[k])
else:
    print(ans[(k-index-1)%(index2-index)+index])

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
tele = list(map(int, input().split()))
reached = [-1 for _ in range(n + 1)]
now = 1
count = 0
reached[1] = 0
cycle = False
while cycle == False:
    now = tele[now - 1] #current town
    count += 1
    if reached[now] == -1:
        reached[now] = count
    else:
        cycle = True
roop_long = count - reached[now]
from_roop_in_town = (k - reached[now]) % roop_long

#print(reached, now, roop_long, from_roop_in_town)

for i in range(from_roop_in_town):
    now = tele[now - 1]
print(now)

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().strip().split()))

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

visited = [-1] * n
now = 0
visited[0] = 0
pre_roop = 0
pos = 0
i = 1
r = 1
while i < k:
    next = a[now]
    #print('roop:',i,now+1,next+1)
    if visited[next] >= 0:
        r = i-visited[next]
        pre_roop = visited[next]
        pos = next
        #print(i,r,pre_roop,next)
        #print(visited)
        break
    else:
        visited[next] = i
        now = next
        #print(i,visited)
        i += 1

if i >= k:
    print(now + 1)
else:
    l = (k - pre_roop) % r
    #print(l)
    i = 0
    p = pos
    while i < l:
        p = a[p]
        i +=1

    print(p+1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
now=1
his=[now]
for i in range(10**6):
  now=a[now-1]
  if i==k-1:
    quit()
  if now in his:
    first=his.index(now)
    break
  his.append(now)
print(his[first+(k-first)%(len(his)-first)])

Submission status: Wrong Answer

Solution code:
looplenn,k = map(int,input().split())
a = [0]+list(map(int,input().split()))

def bin(arr,val):
    left,right = 0,len(arr)-1
    while left<=right:
        mid = (left+right)//2
        if arr[mid]==val: return 1
        elif arr[mid]<val: left = mid + 1
        else: right = mid - 1
    return 0

know = []
now = 1
while not bin(know, now):
    know.append(now)
    now = a[now]

start = a[know[-1]]
for i,num in enumerate(know):
    if num == start:
        loop_init = i
        loop = know[i:]
        break

#print(know,start,loop)

cnt = len(loop)
ans = loop[(k-loop_init)%cnt]
# ans = loop[k%cnt]


print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A = [i-1 for i in A]

check = [0]*N
i = 0
c = 0
check = []
visited = [0]*N
flag = False
while c<=K:
    if visited[i] == 1:
        flag = True
        break
    else:
        check.append(i)
        visited[i] = 1
        i = A[i]
        
X = check[check.index(i):]
print(1+X[(K-c)%len(X)] if flag==True else print(i+1))

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split(' '))
A=list(map(int,input().split(' ')))

load=[1]

for i in range(K):
    if A[load[-1]-1] not in load:
        load.append(A[load[-1]-1])
    else:
        x=load.index(A[load[-1]-1])
        #周期
        f=i-x+1
        #ループ前の数をのぞく
        n=K-x
        #あまり
        l=(n+1)%f
        print(load[x:x+f][l-1])
        break

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().strip().split()))

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

visited = [-1] * n
now = 0
visited[0] = 0
pre_roop = 0
pos = 0
i = 1
r = 1
while i < k:
    next = a[now]
    #print('roop:',i,now+1,next+1)
    if visited[next] >= 0:
        r = i-visited[next]
        pre_roop = visited[next]
        pos = next
        #print(i,r,pre_roop,next)
        #print(visited)
        break
    else:
        visited[next] = i
        now = next
        #print(i,visited)
        i += 1
l = (k - pre_roop) % r
#print(l)
i = 0
p = pos
while i < l:
    p = a[p]
    i +=1

print(p+1)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))

num = 1
l = []
l.append(num)
i = 0
while A[num-1] not in l:
  num = A[num-1]
  l.append(num)
  i += 1
num = A[num-1]
mod = (K-1-i) % (i+1-(l.index(num)))
    
for i in range(mod):
  num = A[num-1]
  
print(num)

Submission status: Wrong Answer

Solution code:
def main(N, K, A):
    i = 0   # 現在地
    lst_memo = []
    set_memo = set([])
    while i not in set_memo:
        lst_memo.append(i)
        set_memo.add(i)
        i = A[i] - 1    # pythonは一つずれる
    key = lst_memo.index(i)
    if K <= key - 1:
        print(lst_memo[K - 1] + 1)
    else:
        roop = lst_memo[key:]
        print(roop[(K - key) % len(roop)] + 1)    # pythonは一つずれる


if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    main(N, K, A)

Submission status: Wrong Answer

Solution code:
def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    l = [0]
    for i in range(n):
        b = a[l[i]]-1
        l.append(b)
        if l.count(b) == 2:
            break
    
    for i in range(len(l)):
        if l[i] == l[-1]:
            loop = l[i:len(l)+1]
            break

    k -= (len(l)-1) - (len(loop)-1)
    ind = loop[k%len(loop)-1]
    
    return ind+1


print(solve())

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
n, k = map(int, input().split())
An = list(map(int, input().split()))
root = deque([1])
check = np.zeros(n, np.int)
check[0] = 1
i = 0
dup = 1
cnt = 1
for _ in range(n):
    temp = An[i]
    if check[temp-1] == 1:
        dup = temp
        break
    root.append(temp)
    check[temp-1] = 1
    i = temp - 1
    cnt += 1
index = root.index(dup)
if index >= k:
    print(root[k-1])
elif index == cnt - 1:
    print(dup)
else:
    print(root[(k-index) % (cnt-index) + index])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

N,K=map(int,input().split())
A=list(map(int,input().split()))


time=1
route=[1]
x=A[0]
Loop=0
x_list=[0]*(N+1)
x_list[1]=1

while x_list[x]==0:
    route.append(x)
    x_list[x]=1
    x=A[x-1]
    time+=1

Loop=time-route.index(x)
a=route.index(x)

        
if Loop==0:
    mod=K%time
    print(route[mod])
    sys.exit()

else:
    mod=(K-a)%Loop
    print(route[mod+a])

Submission status: Wrong Answer

Solution code:
import numpy as np 
N,K = map(int,input().split())
A = list(map(int,input().split()))

t = 1
tpass = [1]
k = 0
j = 1
while j==1:
    temp = A[t-1] 
    if temp in tpass:
        idx = tpass.index(temp)
        l = len(tpass)
        j = -1
    else:
        t = temp
        tpass.append(temp)
        k += 1

try:
    a = K - k
    loop = l - idx
    b = a % loop 
    temp2 = tpass[idx:]
    ans = temp2[b-1]
    print(ans)
except:
    print(t)

Submission status: Wrong Answer

Solution code:
n,k = [int(i) for i in input().split()]
data = [int(i) for i in input().split()]

d = 1
count = 0
loop = []
route = [1]

while count < len(data):
    d = data[d-1]
    if d in route:
        loop = route[route.index(d):]
        break
    else:
        route.append(d)
    count += 1
if len(loop) > 0:
    loop_len = len(loop)
    a = len(route) - loop_len
    if k < a:
        print(route[k-1])
    else:
        print(loop[(k-a)%loop_len])
else:
    print(route[k-1])

Submission status: Wrong Answer

Solution code:
def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    cnt = [-1] * n
    cnt[0] = 0
    ary = []
    now = 1
    ary.append(now)
    if k <= n:
        for i in range(1,k+1):
            now = a[now-1]
            if i == k:
                print(now )
                return
    else:
        for i in range(1,k+1):
            now = a[now-1]
            if cnt[now-1] != -1:
                break
            else:
                cnt[now-1] = i
                ary.append(a[now-1])
        # print(cnt)

        print(ary[cnt[now]+((k-cnt[now]) % (i - cnt[now]))])
        # print(ary)
        # print(cnt[now]+((k-cnt[now]) % (i - cnt[now])))
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
button =list(map(int,input().split()))
loopend = 0
rireki = [0]*N
vir = [0]*N
k = 0
f = 0
button_rireki = list()
for i in range(K):
    button_rireki.append(k)
    if(rireki[k]>0):
        loopend = i
        f = 1
        break
    rireki[k] +=1
    vir[k] = i
    k = button[k]-1
if(f ==0):
    print(button_rireki[-1])
else:
    loopstart = vir[button_rireki[-1]]
    yojo_ = (K-loopstart)%(loopend-loopstart)
    if(yojo_ == 0):
        print(button_rireki[loopend-1])
    else:
        print(button[button_rireki[loopstart+yojo_-1]])
# print(button_rireki,loopstart,loopend,button_rireki[loopend-1],yojo_)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n, k = map(int, input().split())
a = list(map(int, input().split()))
path = []
path.append(1)
x = a[0]
path.append(x)
for i in range(n-2):
    x = a[x-1]
    path.append(x)
#print(path)
c = Counter(path)
roop_st = 0
for key, v in c.items():
    if v == 2:
        roop_st = key
roop_st_idx = 0
roop_fin_idx = n-1
if roop_st != 0:
    roop_st_idx = path.index(roop_st)
    roop_fin_idx = path.index(roop_st, roop_st_idx+1)
#print(roopidx,roopidx2)
k_mod = (k-roop_st_idx) % (roop_fin_idx-roop_st_idx)
print(path[roop_st_idx+k_mod])

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[int(i)-1 for i in input().split()]
ed=[False]*n
go=0
c=0
cc=0

while not ed[go]:
    ed[go]=True
    go=a[go]
    c+=1
ed=[False]*n
while not ed[go]:
    ed[go]=True
    go=a[go]
    cc+=1
go=a[c]
for i in range((k-c)%cc):
    go=a[go]
print(go+1)

Submission status: Wrong Answer

Solution code:
n,k = list(map(int,input().split()))
A = list(map(int,input().split()))
tour=[0]
visited=[0]*n
visited[0]=1
next_town = 0
flag=False
for i in range(n):
    next_town=A[next_town]-1
    if i+1==k:
        flag = True
        ans = next_town
        break
    if next_town==0:
        first_roop_idx = 0
        break
    if visited[next_town]>0:
        first_roop_idx = visited[next_town]
        break
    tour.append(next_town)
    visited[next_town]=i+1
#print(tour)
#print(visited)
#print(first_roop_idx)
if not flag:
    if k<=len(tour):
        ans = tour[k]
    else:
        k-=first_roop_idx
        #print("k=",k)
        if len(tour)-first_roop_idx==0:
            k=0
        else:k=k%(len(tour)-first_roop_idx)
        #print("k=",k)
        ans = tour[first_roop_idx+k]
print(ans+1)
print(flag)

Submission status: Wrong Answer

Solution code:
N,K = list(map(int, input().split()))
A = list(map(int, input().split()))
r = 0
if K <= N:
    current = 0
    for i in range(K):
        current = A[current-1]
    print(current)
else:
    isReturn = [0 for i in range(N)]
    step = 1
    current = 1
    isReturn[current-1] = step
    for i in range(N):
        current = A[current-1]
        step += 1
        if isReturn[current-1] == 0:
            isReturn[current-1] = step
        else:
            r = step - isReturn[current-1]
            break
    
    t = ((K-step) % r) + 1
    for i in range(t):
        current = A[current-1]
        
    print(current)

Submission status: Wrong Answer

Solution code:
from collections import deque
d = deque()

N, K = map(int, input().split())
A = list(map(int, input().split()))

di = [0] * N

d.append(0)
for i in range(N):
    p = d.pop()
    d.append(p)
    d.append(A[p] - 1)

P = []
k = 0
n = 0
for i, v in enumerate(d):
    if (v in P):
        k = i
        n = v
        break
    P.append(v)
    di[v] = i

le = k - di[n]

amari = (K - di[n]) % le

print(d[amari + di[n]] + 1)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
As = list(map(int, input().split()))
maps = {}

for i, a in enumerate(As):
    maps[i] = a - 1

probs = [0] * n
p = 0  # 現在位置
target = 0  # はじめて2回出現する場所
h = 0  # ターゲットの初回出現時のワープ回数
t = 0  # ターゲットの2回目の出現時のワープ回数

# はじめて2回出現する場所(target)と、その時点でのワープ回数を取得
for i in range(n):
    probs[p] += 1
    if (probs[p] == 2):
        target = p
        t = i
        break
    p = maps[p]

# 初回出現位置を取得(めんどうくさいのでもう一回回した。)
p = 0
for i in range(n):
    if (p == target):
        h = i
        break
    p = maps[p]

s = t - h  # 周期
d = (k - h) % s  # targetに到着後にワープすべき回数

# 実際に必要な回数だけワープ
p = 0
for i in range(h + d):
    p = maps[p]

print(p + 1)

Submission status: Wrong Answer

Solution code:
def main(N, K, A):
    i = 0   # 現在地
    lst_memo = []
    set_memo = set([])
    while i not in set_memo:
        lst_memo.append(i)
        set_memo.add(i)
        i = A[i] - 1    # pythonは一つずれる
    key = lst_memo.index(i)
    if K < key:
        print(lst_memo[K - 1] + 1)
    else:
        roop = lst_memo[key:]
        print(roop[(K - key) % len(roop)] + 1)    # pythonは一つずれる


if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    main(N, K, A)

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def main():
    N, K = map(int, input().split())
    A = [int(s) - 1 for s in input().split()]

    pos = 0
    visited = [-1] * N
    visited[0] = 0
    path = [0]
    for i in range(1, N + 1):
        npos = A[pos]
        if i == K:
            print(npos + 1)
        if visited[npos] != -1:
            loop_start = visited[npos]
            cycle = i - visited[npos]
            break

        visited[npos] = i
        path.append(npos)
        pos = npos

    L = loop_start + (K - loop_start) % cycle
    pos = path[L]

    print(pos + 1)

    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
dp = [0] * (n+1)
B = []
f = 1
c = 1
ans = n
bal = 0
for i in range(n):
    if dp[f-1]:
        ans = c-dp[f-1]
        bal = dp[f-1]
        break
    else:
        dp[f-1]+=c
        B.append(f)
        f = A[f-1]
        c+=1
bal-=1
k-= bal
B =B[bal:]
# print(B,bal)
k = k%ans
print(B[k])

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A_dict = {i:a for i,a in enumerate(A,1)}

History = [1]
History_set = {1}
now = 1
for _ in range(N):
    now = A_dict[now]
    if now not in History_set:
        History.append(now)
        History_set.add(now)
    else:
        break
#print(History,now)
e = History.index(now)
#print(e)
#print(History[e:])
loop_num = len(History[e:])
#print(loop_num)
num = (K-e)%loop_num
#print(num)
print(History[e:][num])

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict
d = deque()
di = defaultdict(int)
N, K = map(int, input().split())
A = list(map(int, input().split()))


d.append(0)
for i in range(N):
    p = d.pop()
    d.append(p)
    d.append(A[p] - 1)

P = []
k = 0
n = 0
for i, v in enumerate(d):
    if (v in P):
        k = i
        n = v
        break
    P.append(v)
    di[v] = i

le = k - di[n]

amari = (K - di[n]) % le

print(d[amari + di[n]] + 1)

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict
d = deque()
di = defaultdict(int)
N, K = map(int, input().split())
A = list(map(int, input().split()))


d.append(0)
for i in range(N):
    p = d.pop()
    d.append(p)
    d.append(A[p] - 1)

print(d)
P = []
k = 0
n = 0
for i, v in enumerate(d):
    if (v in P):
        k = i
        n = v
        break
    P.append(v)
    di[v] = i

le = k - di[n]

amari = (K - di[n]) % le

print(d[amari + di[n]] + 1)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
dp = [0] * (n+1)
B = []
f = 1
c = 1
ans = n
bal = 0
for i in range(n):
    if dp[f-1]:
        ans = c-dp[f-1]
        bal = dp[f-1]
        break
    else:
        dp[f-1]+=c
        B.append(f)
        f = A[f-1]
        c+=1
bal-=1
k-= bal
# print(B,bal)
k = k%ans
print(B[k+bal])

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
 
s = [0] * (N+1)
p = 1
h = []
for i in range(2*N+100):
    h.append(p)
    s[p] = 1
    p = A[p]
    
    if i == K:
        print(p)
        exit()
    
    if s[p] != 0:
        break

 
last = h.index(p)
leng = len(h) - last
rem = (K - last) % leng
print(h[last:][rem])

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
i = 1
root = [i]
while not A[i-1] in root:
  root.append(A[i-1])
  i = A[i-1]
loop_start = root.index(A[i-1])
print(root[loop_start + (K - loop_start) % (len(root) - loop_start)])

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
memo = [-1] * (N+1)
checked_num = {1:None}
memo[0] = 1

teleporter = A[0]
memo[1] = teleporter
checked_num[memo[1]] = None
repeat_point = -1
flag = False

for i in range(2, N+1):
    # print(i, checked_num)
    memo[i] = A[teleporter-1]
    teleporter = A[teleporter-1]
    if memo[i] in checked_num and flag == False:
        repeat_point = i
        flag = True
    checked_num[memo[i]] = None

# print(memo)

start_point = memo.index(memo[repeat_point])
repeat = repeat_point - start_point
# print(memo, start_point, repeat_point)

if K <= N:
    print(memo[K])
else:
    mod = (K-start_point) % repeat
    if mod == 0:
        mod = repeat_point
    print(memo[mod])

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
al=[0]+list(map(int,input().split()))
 
# 1から順に探索
visited=[-1]*(1+n)
cl=[0]*(1+n)
visited[1]=0
c=0
now=1
t=0
 
start=0
 
for i in range(1,n+1):
    if visited[al[now]]==-1: # まだきてない
        visited[al[now]]=0
        c+=1
        cl[al[now]]=c
        now=al[now]
    else:  
        start=cl[al[now]]
        t=i-start
        break

if start>=k:
    print(cl.index(k))
else:

    print(cl.index(start+(k-start)%t))

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = [0]+list(map(int,input().split()))

def bin(arr,val):
    left,right = 0,len(arr)-1
    while left<=right:
        mid = (left+right)//2
        if arr[mid]==val: return 1
        elif arr[mid]<val: left = mid + 1
        else: right = mid - 1
    return 0

know = []
now = 1
while not bin(know, now):
    know.append(now)
    now = a[now]

start = a[know[-1]]
for i,num in enumerate(know):
    if num == start: loop = know[i:] ; break

#print(know,start,loop)

cnt = len(loop)
if k>=len(know): k -= len(know)
ans = loop[k%cnt]


print(ans)

Submission status: Wrong Answer

Solution code:
import sys

# print('input >>')
N, K = map(int,(input().split()))
As = list(map(lambda x: int(x)-1,(input().split())))

now = 0
# move = 1
nows = [0]
p = 0

# print('-----output-----')
while True:
    # move += 1
    now = As[now]
    if now in nows:
        p = now
        rep_start = nows.index(now)
        nows = nows[::-1]
        move = nows.index(now)+1
        break
    nows.append(now)

now = 0
for i in range(rep_start):
    now = As[now]

if rep_start > K:
    sys.exit()

K -= rep_start
K %= move
now = p

for i in range(K):
    now = As[now]

print(now+1)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))

C=[1]
p=0

for i in range(N):
    C.append(A[C[i]-1])
    p+=1
    if C[i+1]==1:
        break

print(C[K%p])

Submission status: Wrong Answer

Solution code:
N,K = list(map(int, input().split()))
A = list(map(int, input().split()))
r = 0
if K <= N:
    current = 0
    for i in range(K):
        current = A[current-1]
    print(current)
else:
    isReturn = [0]*(N)
    step = 1
    current = 1
    isReturn[current-1] = step
    for i in range(N):
        current = A[current-1]
        step += 1
        if isReturn[current-1] == 0:
            isReturn[current-1] = step
        else:
            r = step - isReturn[current-1]
            break
    
    t = (K-step) % r
    for i in range(t+1):
        current = A[current-1]
        
    print(current)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
d2 = []
hist=[-1]*n
hist[0] = 0
cur = 1
d2.append(1)
st_idx = 0
rp_lgt = 0
for i in range(n):
  cur = a[cur-1]
  if hist[cur-1] >= 0 :
     st_idx = hist[cur-1] 
     rp_lgt = i - st_idx + 1
     break
  else:
    d2.append(cur)
    hist[cur-1] = i
wk = k - st_idx
md = wk % rp_lgt
if k < st_idx:
  ans = d2[k]
else:
  ans = d2[md+st_idx]
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = tuple(map(int, input().split()))
 
point = 1
cnt = 1
m = 0
mm = 0
ind = 0
l = [1]
for i in range(n):
    point = a[point-1]
    cnt += 1
    if point in l:
        mm = i+1
        ind = l.index(point)
        m = cnt - 1 - ind
        break
    l.append(point)
 
if k >= mm:
    print(l[(k-mm)%m+ind])
else:
    print(n)