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 = list(map(int, input().split()))

m = {}
for i, a in enumerate(A):
    m[i+1] = a

visited = []
cycle = set()
current_city = 1
visited.append(current_city)
cycle.add(current_city)
cycle_start_index = -1
while 1:
    current_city = m[current_city]
    if current_city in cycle:
        cycle_start_index = visited.index(current_city)
        break
    else:
        visited.append(current_city)
        cycle.add(current_city)

cycle_before = visited[:cycle_start_index]
cycle_after = visited[cycle_start_index:]
if len(cycle_before) < K:
    print(cycle_after[(K - len(cycle_before)) % len(cycle_after)])
else:
    print(cycle_before[K - 1])

Submission status: Wrong Answer

Solution code:
# トポロジカルソートで解決できそうだけどわからん！
n, k = map(int, input().split())

field = [(i, j) for i, j in zip(range(n), list(map(int, input().split())))]

#%%
town = 0
visited = [0] # 訪問済みの街を格納
while True:
    trans = field[town][1] - 1
    n_town = field[trans][0]
    if n_town not in visited:
        visited.append(n_town)
    else:
        st_circ = visited.index(n_town)
        break
    town = n_town

#%%
# ループ開始前まで
mae = len(visited[:st_circ])
circ = len(visited[st_circ:])

if k < mae:
    ans = visited[k-1]
else:
    idx = (k - mae) % circ
    ans = visited[idx + mae]

print(ans+1)

Submission status: Wrong Answer

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

cache={}
log=[]
A = list(map(lambda x:int(x)-1, input().split(' ')))

now=0

while(True):
  log.append(now)
  cache[now]=1
  now=A[now]
  if(cache.get(now)):break

loop_start=log.index(now)
loop_end=len(log)
loop=loop_end-loop_start
#print(loop_end-loop_start,loop_start)
print(loop_start,loop_end,log)
if len(log) >= loop:
  if loop_end>K:
    print(now)
  else:
    print(log[K%loop]+1)
else:
  print(log[K%loop+loop]+1)

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=list(map(int,input().split()))
for i in range(N):
    a[i]-=1
if a[0]==1:print(1);exit()
c=dict()
visited=[False]*N
visited[0]=True
c[0]=0
cnt=0
dap=0
n=0
b=[0]
while True:
    n=a[n]
    if visited[n]:
        dap=c[n] 
        break
    visited[n]=True
    b.append(n)
    cnt+=1
    c[n]=cnt
l=len(c)
print(b[(k-dap)%(l-dap)+dap]+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
for _ in range(N):
  count += 1
  visited[i] += 1
  if visited[i] == 2:
    end = count-1
    break
  rootin[count] = A[i]
  i = A[i]-1
start = 0
for i in range(N):
  if rootin[i] == rootin[end]:
    start = i
    break
od = len(rootin[:start])
root = len(rootin[start:end])
if K > od:
  K -= od
  ans = rootin[start+K%root]
else:
  ans = rootin[K-1]
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
from collections import OrderedDict

n,k = map(int,input().split())
L = list(map(int,input().split()))
od = collections.OrderedDict()

t = 1
r = 0
i = 0
c = 0
for j in range(n*2):
    #print(L2)
    t = L[t-1]
    if ｔ in od:
        l = list(od.keys())
        i = l.index(t)
        r = len(od) - i
        break
    else:
        od[t] = t
#print(r)
#print(i)

k = (k - i)%r
#print(k)
l = list(od.keys())
print(l[i+k-1])

Submission status: Wrong Answer

Solution code:
N,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(N):
    a[i]-=1
if a[0]==1:print(1);exit()
c=dict()
visited=[False]*N
visited[0]=True
c[0]=0
cnt=0
dap=0
n=0
b=[0]
while True:
    n=a[n]
    if visited[n]:
        dap=c[n] 
        break
    visited[n]=True
    b.append(n)
    cnt+=1
    c[n]=cnt
l=len(c)
print(b[(k-dap)%(l-dap)+dap]+1,b)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
N=list(map(int,input().split()))
a={}
 
b=1
a[1]=1
count=1
while(True):
  count+=1
  b=N[b-1]
  #print(b)
  if b in a:
    #print(a)
    #print(b)
    #print(count)
    cycle=count-a[b]
    rest=K-count+1
    ans=rest%cycle
    for i in range(ans-1):
      b=N[b-1]
    print(b)
    break
  a[b]=count
  if count==K+1:
    print(b)
    break

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

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

Submission status: Wrong Answer

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

pos = 0
kiseki = [0] * (N+1)
for i in range(N):
    pos = A[pos] - 1
    kiseki[i+1] = pos

tail = kiseki.pop()
past = kiseki.index(tail)
print(kiseki[past + (K - past) % (N - past)] + 1)

Submission status: Wrong Answer

Solution code:
N,K= map(int, input().split())
A = list(map(int,input().split()))
if(A[0] == 1):
    print(1)
    exit(0)
p = 1
P = []
start,stop = 0, 0
for i in range(N):
    p = A[p-1]
    if p in P:
        start = P.index(p)
        break
    P.append(p)
stop = len(P)-1
if len(P) == K:
    print(B[-1])
else:
    del P[0:start]
    Z = (K-start-1)%((stop-start+1))
    print(P[Z])

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
lst = list(map(int, (input().split())))
lst = [_ - 1 for _ in lst]

visited = [0] * n
flg = 1
i = 0
now = 0
while flg:
    if visited[now] == 0:
        i += 1
        visited[now] = i
        now = lst[now]
    else:
        flg = 0

k_bk = k - (i - visited[now])
k_bk =  k_bk // i

lft = k - i* k_bk

if lft ==0:
    print(now+1)
else:
    for _ in range(lft):
        now = lst[now]
    print(now+1)

Submission status: Wrong Answer

Solution code:
from collections import OrderedDict

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

returned = None
i = 0
aa = 0
visited = OrderedDict([(0, 0)])
while i < n:
    aa = a[aa] - 1
    i = i + 1
    if aa in visited:
        returned = (visited[aa], i)
        break
    visited[aa] = i

k = ((k - returned[0]) % (returned[1] - returned[0])) + returned[0]

print(list(visited.keys())[k] + 1)

Submission status: Wrong Answer

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

journey = [1]

for i in range(2 * n + 100):
    next = a[journey[-1]]
    journey.append(next)

if k < n+1:
    print(journey[k])
    exit()

loop_end = journey[n]

loop_start = n - 1

while (journey[loop_start] != loop_end):
    loop_start -= 1

period = loop_end - loop_start
k %= period

while k < n:
    k += period

print(journey[k])

Submission status: Wrong Answer

Solution code:



arr1 = list(map(int,list(input().split())))
arr2 = list(map(int,list(input().split())))
arr2.insert(0,0)

N=arr1[0]
K=arr1[1]

cnt=0

x=1
times=0
lst=[]
lst.append(1)
for i in range(N):
	times+=1
	x=arr2[x]
	if x in lst:
		dblvalue=x
		lst.append(x)
		break
	else:
		lst.append(x)

first=lst.index(dblvalue)
times=len(lst)-lst.index(dblvalue)-1

last=(K - first)%times

#teleport
x = dblvalue
if last==0:
	pass
else:
	for _ in range(times-1):
		x=arr2[x]
print(x)

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*2):
        ans.append(a[now])
        now=a[now]-1
#print(ans)

#変更
passed = set()
ac = -1
for i in range(len(ans)):
    if ans[i] in passed:
        ac = ans[i]
        break
    else:
        passed.add(ans[i])
#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))
#print(ans)
if k < index:
    print(ans[k])
else:
    k -= (index + 1)
    ans = ans[index:]
    print(ans[k % (index2 - index)])

Submission status: Wrong Answer

Solution code:
'''
.append(要素) リストに要素を追加
.extend(リスト) リストを連結する
.insert(場所,要素) 指定した場所に要素追加
del 配列名[場所]
-1で末尾で末尾から一つ前

sort()
sorted(reverse=true)

配列の初期化
配列名=[a]*n+[b]*m

Decimal()
'''

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
from functools import reduce
from operator import mul
from collections import Counter
import itertools
import fractions
import sys

t = [int(s) for s in stdin.readline().rstrip().split()]
n = t[0]
k = t[1]
Ak = [int(s) for s in stdin.readline().rstrip().split()]

data = [1]
tmp = 0
for el in Ak:
    data.append(Ak[tmp])
    tmp = Ak[tmp] - 1
print(data)
head = 1
mark = [int(s) for s in '0' * n]
used = []
for el in data:
    used.append(el)
    if (mark[el-1] == 1):
        head = el
        break
    mark[el - 1] = 1
base = used[:used.index(head)]
circle = used[used.index(head):]
if circle[0] == circle[-1]:
    del circle[-1]
print(data[len(base)+(k-len(base)) % len(circle)])

Submission status: Wrong Answer

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

city_idx = 0
reached_city = [0] * N
cycle = [0]
reached_city[0] = 1
for k in range(N):
    city_idx = A[city_idx] - 1
    if reached_city[city_idx] == 1:
        offset = cycle.index(city_idx)
        loop_step = k - offset + 1
        break
    else:
        reached_city[city_idx] = 1
        cycle.append(city_idx)
if K < offset:
    print(cycle[K])
elif offset == K:
    print(city_idx)
else:
    pos = (K - offset) % loop_step
    print(cycle[offset + pos] + 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)

#変更
passed = set()
ac = -1
for i in range(len(ans)):
    if ans[i] in passed:
        ac = ans[i]
        break
    else:
        passed.add(ans[i])
#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))
#print(ans)
if k < index:
    print(ans[k])
else:
    k -= (index + 1)
    ans = ans[index:]
    print(ans[k % (index2 - index)])

Submission status: Wrong Answer

Solution code:
N,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(N):
    a[i]-=1
if a[0]==0:print(1);exit()
c=dict()
visited=[False]*N
visited[0]=True
c[0]=0
cnt=0
dap=0
n=0
b=[0]
while True:
    n=a[n]
    if visited[n]:
        dap=c[n] 
        break
    visited[n]=True
    b.append(n)
    cnt+=1
    c[n]=cnt
l=len(c)
print(b[(k-dap)%(l-dap)+dap]+1)

Submission status: Wrong Answer

Solution code:
import sys

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

z = 1
p = [1]
for i in range(n):
    z = a[p[i]-1]
    if z in p:
        p.append(z)
        break
    p.append(z)

# 周期の来る前の回数
num = p.index(p[-1])

p = p[num:]

# 周期
pn = len(p)-1

k -= num

# 回数/周期のあまり
anum = k%pn
print(p[anum])

Submission status: Wrong Answer

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

#n=6
#k=727202214173249351
#a=[6, 5, 2, 5, 3, 2]

#n=4
#k=5
#a=[3,2,4,1]

if n<k:
    ai=1
    aj=[]
    for i in range(min(n,k)):
        aim=ai
        ai=a[ai-1]
#        print(ai,aj)
        if ai in aj:
            ic2=i
            ai2=ai
#            print(ic2,ai,aj)
            break
        else:
            aj.append(ai)

    ai=1
    for i in range(min(n,k)):
        ai=a[ai-1]
        if ai==ai2:
            ic1=i
            break

    icyc=ic2-ic1
    k2=(k-ic1)%icyc+ic1
else:
    ic1=0
    icyc=1
    k2=k
    
ai=1
for i in range(k2):
    ai=a[ai-1]
        
print(ai)

Submission status: Wrong Answer

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

num = 1
l = [1]
i = 0
while A[num-1] not in l:
  num = A[num-1]
  l.append(num)
  i += 1
else:
  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:
n,k,*a=map(int,open(0).read().split())
b=[1]
s_b=set()
s_b|={1}
for i in range(n+1):
  if a[b[-1]-1] in s_b:
    idx=b.index(a[b[-1]-1])
    break
  else:
    b.append(a[b[-1]-1])
    s_b|={b[-1]}
mod=len(b[idx:])
d=len(b[:idx])
print(b[d+(k-d)%mod])

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)

#変更
passed = set()
ac = -1
for i in range(len(ans)):
    if ans[i] in passed:
        ac = ans[i]
        break
    else:
        passed.add(ans[i])
#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))
#print(ans)
if k < index:
    print(ans[k])
else:
    k -= index
    ans = ans[index:]
    print(ans[k % (index2 - index - 1)])

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) for s in input().split()]

    pos = 1
    order = [-1] * (N+1)
    order[1] = 0
    s = [1]
    for i in range(1, N + 1):
        npos = A[pos-1]
        if i == K:
            print(npos)
        if order[npos] != -1:
            l = order[npos]
            c = i - order[npos]
            break

        order[npos] = i
        s.append(npos)
        pos = npos

    L = l + (K - l) % c
    pos = s[L]

    print(pos)

    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,K= map(int, input().split())
a =list(map(int, input().split()))
root = []
root.append(1)
tmp =1
key = 0
for _ in range(N):
    key = a[tmp-1]
    if key in root:
        break
    root.append(a[tmp-1])
    tmp = a[tmp-1]
first_length = len(root)-len(root[root.index(key):N])
T_root = root[root.index(key):N]
if len(root)>=K:
    print(root[K-1])
else:
    print(T_root[(K-first_length)%len(T_root)])

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
l = list(map(int,input().split()))
memo1 = [0]*(n+1)
memo2 = [0]*1000000
tmp = 0
t = 1
index = 0

for i in range(10000000):
    tmp = l[t-1]
    if memo1[t-1] != tmp:
        memo1[t-1] = tmp
        memo2[i] = tmp
        t = tmp 
    else:
        memo2[i] = tmp
        indexes = [i for i, x in enumerate(memo2) if x == memo1[t-1]]
        index = indexes[1] - indexes[0]
        break

tmp2 = k - indexes[1]
if tmp2 <= 0:
    print(memo2[k-1])
else:
    tmp2 = tmp2%index
    if tmp2 == 0:
        print(memo1[indexes[0]])
    else:
        print(memo2[indexes[0]+tmp2-1])

Submission status: Wrong Answer

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

m = {}
for i, a in enumerate(A):
    m[i+1] = a

visited = []
cycle = set()
current_city = 1
visited.append(current_city)
cycle.add(current_city)
cycle_start_index = -1
while 1:
    current_city = m[current_city]
    if current_city in cycle:
        cycle_start_index = visited.index(current_city)
        break
    else:
        visited.append(current_city)
        cycle.add(current_city)

cycle_before = visited[:cycle_start_index]
cycle_after = visited[cycle_start_index:]
ans = visited[(K - len(cycle_after)) % len(cycle_after)]
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
 
A = list(map(int,input().split()))
 
now = 0
tele = [0]
i = 1
tele2 = dict()
while True:
  now = A[now] - 1
  i += 1
  if now in tele2:
    num = tele.index(now)
    epoch = i - num - 1
    e_list = tele[num:]
    break
  tele.append(now)
  tele2[now] = 1
roop = int((K-num)/epoch)
amari = (K-num)%epoch
print(e_list[amari] + 1)

Submission status: Wrong Answer

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

s = 0
seen = [False for _ in range(n)]
d = [0]
cy = -1
for _ in range(n):
    seen[s] = True
    s = a[s]-1
    if seen[s]:
        cy = s
        break
    d.append(s)

if cy == -1:
    print(d[k-1])
    exit()

noncyi = d.index(cy)
cyi = len(d) - noncyi
if k < noncyi:
    print(d[k-1])
else:
    k -= noncyi
    print(d[noncyi + k%cyi]+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+1))%loop
        print(List.index(i - loop + afterloop)+1)
        exit()

print(next)

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]
visited = [False]*n
route = []
now = 0
hop = 0
while visited[now]==False:
    visited[now]=True
    route.append(now)
    now = a[now]
    hop+=1
loop_st = 0
for r in route:
    if r==now: break
    loop_st+=1
loop = route[loop_st:]
if k < loop_st:
    print(route[k])
else:
    k-=loop_st
    print(loop[k%len(loop)]+1)

Submission status: Wrong Answer

Solution code:
a,b=map(int, input().split())
c=list(map(int, input().split())) 

l = [1]
tmp = 1
for i in range(a):
    l.append(c[tmp-1])
    tmp = c[tmp-1]

#print(l)
s = 0    
for i in range(a):
    d = l.count(l[i])
    if d > 1:
        s = l[i]
        break

flg = 0
h = 0
t = 0
for i in range(a):
    if s == l[i] and flg == 0:
        h = i + 1
        flg = 1
    elif s == l[i]:
        t = i + 1

#print(s,h,t)
l2 = l[h-1:t-1]
if s == 1:
    id = b % (t - 1)
    print(l2[id])
else:
    id = (b - h + 1) % (t - h - 1)
    print(l2[id-1])

Submission status: Wrong Answer

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

limit = K
now = 1
log = []
count = 0

#print("通過0",now,limit,count,log)

while limit > 0 and A[now - 1] not in log:
    if 1 not in log:
        log.append(1)
    now = A[now - 1]
    log.append(now)
    limit -= 1
    count += 1
    #print("通過1",now,limit,count,log)

if limit > 0:
    #input("stop")
    log2 = log[log.index(now) - 2:]
    limit = limit % len(log2)
    #print("通過2",now,limit,count,log,log2)
    while limit > 0:
        now = A[now - 1]
        limit -= 1
        count += 1
        #print("通過3",now,limit,count,log,log2)

print(now)

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
for _ in range(N):
  count += 1
  visited[i] += 1
  if visited[i] == 2:
    end = count
    break
  rootin[count] = A[i]
  i = A[i]-1

start = 0
for i in range(len(rootin[:end])):
  if rootin[i] == rootin[end-1]:
    start = i
    break
od = len(rootin[:start])
root = len(rootin[start:end])-1

K -= od
ans = rootin[start+K%root]
print(ans)

Submission status: Wrong Answer

Solution code:

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

#n=6
#k=727202214173249351
#a=[6, 5, 2, 5, 3, 2]

#n=4
#k=5
#a=[3,2,4,1]

if n<k:
    ai=1
    aj=[]
    for i in range(min(n,k)):
        aim=ai
        ai=a[ai-1]
#        print(ai,aj)
        if ai in aj:
            ic2=i
            ai2=ai
#            print(ic2,ai,aj)
            break
        else:
            aj.append(ai)

    ai=1
    for i in range(min(n,k)):
        ai=a[ai-1]
        if ai==ai2:
            ic1=i
            break

    icyc=ic2-ic1
    k2=(k-ic1)%icyc+ic1
else:
    ic1=0
    icyc=1
    k2=k
    
ai=1
for i in range(k2):
    ai=a[ai-1]
        
print(ai)

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+1))%loop
        print(List.index(i - loop + afterloop))
        exit()

print(next)

Submission status: Wrong Answer

Solution code:
N = [int(e) for e in input().split()]
nums = [int(t) for t in input().split()]
count=[]
h = 0
k=0
check = []
for i in range(N[0]):
    count.append(0)
while h<N[0]:
    t = nums[k]
    if(count[t-1] == 1):
        break
    else:
        check.append(t)
        count[t-1] += 1
    k = t -1
    h+=1
s = check.index(t)
ans = (N[1] - s)%(len(check)-s)
ans1 = check.index(t) - 1 + ans
print(check[ans1])

Submission status: Wrong Answer

Solution code:
'''
.append(要素) リストに要素を追加
.extend(リスト) リストを連結する
.insert(場所,要素) 指定した場所に要素追加
del 配列名[場所]
-1で末尾で末尾から一つ前

sort()
sorted(reverse=true)

配列の初期化
配列名=[a]*n+[b]*m

Decimal()
'''

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
from functools import reduce
from operator import mul
from collections import Counter
import itertools
import fractions
import sys

t = [int(s) for s in stdin.readline().rstrip().split()]
n = t[0]
k = t[1]
Ak = [int(s) for s in stdin.readline().rstrip().split()]

data = [1]
tmp = 0
for el in Ak:
    data.append(Ak[tmp])
    tmp = Ak[tmp]-1
head = 1
mark = [int(s) for s in '0' * (n + 1)]
used = []
for el in data:
    used.append(el)
    if (mark[el-1] == 1):
        head = el
        break
    mark[el - 1] = 1
base = used[:used.index(head)]
circle = used[used.index(head):]
if circle[0] == circle[-1]:
    del circle[-1]
print(used[len(base)+(k-len(base)) % len(circle)])

Submission status: Wrong Answer

Solution code:
def resolve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    roop=0
    iti=0
    rirekin=0
    rireki=[]
    while roop==0:
        iti=a[iti]-1
        for i in range(len(rireki)):
            if rireki[i]==iti:
                mae=i
                Mae=rireki[:mae]
                rireki=rireki[mae:]
                roop=rirekin-mae
                break
        rireki.append(iti)
        rirekin+=1
    if k <= mae:
        print(Mae[k-1]+1)
    else:
        k-=mae
        print(rireki[(k%roop)-1]+1)
resolve()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
lst = list(map(int, (input().split())))
lst = [_ - 1 for _ in lst]

visited = [0] * n
flg = 1
i = 0
now = 0
while flg:
    if visited[now] == 0:
        i += 1
        visited[now] = i
        now = lst[now] 
    else:
        break

k_bk = k - (i - visited[now])
k_bk =  k_bk // i

lft = k - i* k_bk

if lft ==0:
    print(now+1)
else:
    for _ in range(lft):
        now = lst[now]
    print(now+1)

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) for s in input().split()]

    pos = 1
    visited = [-1] * (N+1)
    visited[1] = 0
    path = [1]
    for i in range(1, N + 1):
        npos = A[pos-1]
        if i == K:
            print(npos)
        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)

    return


if __name__ == '__main__':
    main()

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

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

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(ary[cnt[now-1] - 1 +((k-cnt[now-1]) % (i - cnt[now-1]))])
        # print(now)
        # print(i)
        # print(cnt)
        # print(ary)
        # print(cnt[now]+((k-cnt[now]) % (i - cnt[now])) + 1)
if __name__=='__main__':
    main()

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)

print('実行速度計測')

"""
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:
N,K = map(int,input().split())
As = list(map(int,input().split()))
towns = [0]*N
route = [0]
pre = 0
i = 0
towns[0] = 1
for _ in range(N):
    i = As[i]-1
    if towns[i]>0:
        pre = route.index(i)
        route = route[pre:]
        break
    route.append(i)
    towns[i] = 1
mod = len(route)
print(route[(K-pre)%mod]+1)

Submission status: Wrong Answer

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

a = [0] + list(map(int, input().split()))
a1 = [0] * (n+1)

step = 1
start = 0
while(True):
    start += 1
    a1[step] += 1
    step = a[step]
    if a1[step] == 1:
        break
c = step
gap = 0
while(True):
    gap += 1
    step = a[step]
    if step == c:
        break
k = (k-start) % gap
result = c
for _ in range(k):
    result = a[result]

print(result)

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回目の出現時のワープ回数

if (maps[0] == 0):
    print(1)
    exit

# はじめて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:
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)

#変更
passed = set()
ac = -1
for i in range(len(ans)):
    if ans[i] in passed:
        ac = ans[i]
        break
    else:
        passed.add(ans[i])
#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 = [int(i) for i in input().split()]
tmp=0
tmplist=[0]
#loopしてない判定
loopinter=n
loopstart=0
for i in range(k):
    tmp=a[tmp]-1
    if tmp not in tmplist:
        tmplist.append(tmp)
    else:
        loopstart = tmplist.index(tmp)
        loopinter = len(tmplist)-tmplist.index(tmp)
        break
if k>loopstart:
    for i in range((k-loopstart)%loopinter):
        tmp=a[tmp]-1
else:
    for i in range(k%loopinter):
        tmp=a[tmp]-1
print(tmp+1)

Submission status: Wrong Answer

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

#すでに移動したことのある場所
already = [False] * N
step = 0
already[0] = True
now = A[A[0] - 1]
count = 1
while(already[now-1] != True):
    count += 1
    already[now - 1] = True
    now = A[now - 1]
count += 1

#ループに入るまで何回ステップがあったか調べる
if(now-1 == 0):
    step = 0
    loop = N
else:
    step = 1
    temp = A[A[0] - 1]
    while(temp != A[now - 1]):
        temp = A[temp - 1]
        step += 1
    cycle = count - step
    loop= K % cycle
    
temp = A[A[0] - 1]
for i in range(step + loop -1):
    temp = A[temp - 1]
print(temp)