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:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,K = inputMap()
	A = inputList()

	mati = [0 for i in range(N)]
	for i,val in enumerate(A):
		mati[i] = val-1

	tugi = 0
	ans = []
	cnts = 0
	for i in range(K):
		tugi = mati[tugi]
		cnts += 1
		if tugi in ans:
			break
		else:
			ans.append(tugi)

	tmp = len(ans)
	kotae = (K+2) % (tmp)

	#print(cnts)
	#print(kotae)
	#print(ans)
	print(ans[kotae]+1)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

n,k=map(int, input().split())
a=list(map(int, input().split()))
isUsed=[False]*n

path = [1]
#isUsed[0] = True

i = 1
while(True):
    idx = i-1
    if isUsed[idx]: #既に行ったことがある町であれば
        #print("行ったことのある町です")
        #print("i", i)
        start = path.index(i)
        break
    else:
        isUsed[idx] = True
        path.append(a[idx])
        #print(path)
        i = a[idx]


#print(start)
#print(len(path)-1)
num = len(path) - 1 - start
lis_mod = path[start:start+num]

mod = len(lis_mod)

#print("k-start",k-start)
tmp = (k-start)%mod
#print("k-start % mod", tmp)
print(lis_mod[tmp])

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = [int(a) - 1 for a in input().split()]
visited = [False] * N

cur = 0
visited[cur] = True
nxt = A[cur]
turn = 1
path = [[cur, turn]]
while True:
    if visited[nxt]:
        break
    cur = nxt
    visited[cur] = True
    nxt = A[cur]
    turn += 1
    path.append([cur, turn])
st = A[path[-1][0]]
st_turn = 1
for x in path:
    if x[0] == st:
        st_turn = x[1]
        break
fq = path[-1][1] - st_turn + 1
go = (K - (st_turn - 1)) % fq
ans = nxt
while go > 0:
    ans = A[ans]
    go -= 1
print(ans + 1)

Submission status: Wrong Answer

Solution code:
n,K=list(map(int,input().split()))
a = list(map(int,input().split()))
b = []
c = [0]*len(a)

k=0
for i in range(n):
    b.append(a[k])
    k=a[k]-1
    if c[a[k]-1]==0:
        c[a[k]-1]=1
    else:
        b.pop(-1)
        break
d=len(b)
e=K%d
print(b[e-1])

Submission status: Wrong Answer

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

check = [0] * (n+10)
res = []
next = 0

for i in range(100):
    if check[next] == 0:
        check[next] = 1
        next = li[next]-1
    elif check[next] == 1:
        check[next] += 1
        res.append(next+1)
        next = li[next]-1
    else:
        cnt = len(res)
        k -= check.count(1)
        amari = k%cnt
        print(res[amari])
        break

Submission status: Wrong Answer

Solution code:
# # for i in range(m):
# s = input()
# t = input()
# n = len(s)
# m = len(t)
# # print(s,t,n,m)
# if n+1==m:
# 	for i in range(n):
# 		# print(s[i], t[i])
# 		if s[i]!=t[i]:
# 			print("No")
# 			break
# 	else:
# 		print("Yes")
# else:
# 	print("No")
	# l, r = [int(j)-1 for j in input().split()]
	################
# def fun(a,b,c,k):
# 	ans =0 
# 	if k<=a:
# 		return k
# 	else:
# 		ans = a
# 		k-=a
# 	if k<=b:
# 		return ans
# 	else:
# 		k-=b
# 	# if k<=c:
# 	# print(ans, c)
# 	return ans-min(c,k)
# a,b,c,k = [int(j) for j in input().split()]
# # l = [a,b,c]
# # j = 0
# print(fun(a,b,c,k))
################################

# while(k>0):
# 	a = min(k, l[j])
# 	k-=a

#######################

n,k = [int(j) for j in input().split()]
a = [int(j) for j in input().split()]
s = dict({1:0})
l = [1]
temp = 1
ct = 0
rep = None
while(True):
	ct+=1
	# print(temp)
	temp = a[temp-1]
	if temp in s:
		rep = s[temp]
		break
	else:
		s[temp]=ct
		l.append(temp)
if rep==None:
	print(l[k])
else:
	n = len(l)
	print(l[rep-1+(k-rep+1)%(n-rep)])
# print(l[s[a[ct]]-1+(k-s[a[ct]]+1)%(-1*s[a[ct]]+ct+1)])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

N, K = MII_split()
As = LII_split()

# search loop
visited = [False for _ in range(N)]
start = 1
visited[0] = True
loop = [start]
cur = start
for _ in range(N):
    nex = As[cur - 1]
    # print(cur)
    if not visited[nex - 1]:
        loop.append(nex)
        visited[nex - 1] = True
        cur = nex
    else:
        start_idx = loop.index(nex)
        before_num = start_idx
        befores = loop[:start_idx + 1]
        loop = loop[start_idx:]

        break

# print(loop)
# return
if K < before_num:
    print(befores[K-1])
else:
    K -= before_num
    idx = K % len(loop)
    print(loop[idx])

Submission status: Wrong Answer

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

ls = [0]*N

count = 0
now = 0
roop = 0

while ls[now] == 0:
    ls[now] = 1
    now = A[now] - 1
    count += 1

k = K - count

while ls[now] == 1:
    ls[now] = 2
    now = A[now] - 1
    roop += 1
k = k%roop

while k > 0:
    now = A[now]-1
    k -= 1

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

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

        seen.add(npos)
        visited[npos] = i
        pos = npos

    L = loop_start + (K - loop_start) % cycle
    pos = 0
    for i in range(L):
        pos = A[pos]

    print(pos + 1)

    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

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

visited = [False] * n
visited[0] = True
l = [1]
while True:
    x = A[l[-1]-1]
    if visited[x-1]:
        break
    l.append(x)
    visited[x-1] = True
# print(l[l.index(x):])
if A[x-1] == x:
    print(x)
else:
    print(l[l.index(x):][(k-l.index(x)) % len(l[l.index(x):])])

Submission status: Wrong Answer

Solution code:
n, k = list(map(int,input().strip().split()))
a = list(map(int,input().split()))
b = ["1"]
i = int(1)
c = "0"
j = int(0)
temp = 0
while temp == 0:
    i = a[i - 1]
    if str(i) in b:
        temp = 1
    b += str(i)
    c = str(i)
while temp == 1:
    if c == b[j]:
        temp = j
    j += 1
x = len(b) - temp - 1
y = len(b) - x - 1
ans = (k - y) % x
anss = a[ans + y]
print(anss)

Submission status: Wrong Answer

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

#ループする場合
flag=[0]*N
patt=[]
i=0
while True:
    patt.append(i)
    if flag[i]==1:
        #del patt[-1]
        break
    flag[i]=1
    i=A[i]-1

srt = patt.index(patt[-1])
end = len(patt)-2
ptrn = patt[srt:end+1]

B = (K-srt) % len(ptrn)
if B==0:
    print(ptrn[0]+1)
else:
    print(ptrn[B]+1)

Submission status: Wrong Answer

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

while True:
    goto=A[tour[-1]-1]
    tour.append(goto)
    if visited[goto-1]:
        break
    visited[goto-1]=1

#print(tour)
    
before=0
shuuki=1
for i in range(len(tour)):
    if tour[i]==tour[-1]:
        before=i
        shuuki=len(tour)-i-1
        break

#print(before,shuuki)

if K<=len(tour):
    print(tour[K-1])
else:
    K-=before
    K%=shuuki
    print(tour[before+K])

Submission status: Wrong Answer

Solution code:
#coding: utf-8
from collections import Counter
N, K = map(int, input().split())
A = list(map(int, input().split()))
visited = [False for _ in range(N)]
state = 0
heiro = [0]
visited[0] = True
while True:
    state = A[state]-1
    heiro.append(state)
    # print(state)
    if visited[state]:
        break
    visited[state] = True
cnter = dict(Counter(heiro))
for k in cnter.keys():
    if cnter[k] == 2:
        v = k
        break
idx = heiro.index(v)
K -= idx
ans = heiro[idx:-1][K % (len(heiro) - idx - 1)] + 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
d={}
cnt=[]
m=0
ans=0
for i in range(2*n):
  if a[m] in d:
    ans+=1
    cnt.append(a[m])
    if ans==k:
      print(a[m])
    break
  else:
    d[a[m]]=0
    cnt.append(a[m])
    ans+=1
    if ans==k:
      print(a[m])
      break
    m=a[m]-1
if ans!=k:
  if cnt[-1]==cnt[-2]:
    print(cnt[-1])
  else:
    print(cnt[(k-ans)%len(cnt)])

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    def int_0(num):
        return int(num) - 1

    N, K = map(int, input().split())
    A = tuple(map(int_0, input().split()))
    
    # dfs
    INF = 10 ** 18
    visited = [False] * N
    dist = [INF] * N
    info  = {}
    def dfs(s):
        stack = deque()
        stack.append(s)
        visited[s] = True
        dist[s] = 0
        while stack:
            now = stack.pop()
            visited[now] = True
            nv = A[now]
            if visited[nv] == True:
                info["start"] = nv
                info["length"] = dist[now] - dist[nv] + 1
                info["f"] = dist[nv]
                break
            else:
                dist[nv] = dist[now] + 1
                stack.append(nv)
    dfs(0)

    if K <= N:
        now = 0
        for _ in range(K):
            now = A[now]
        print(now+1)

    K -= info["f"]
    K %= info["length"]

    now = info["start"]
    for _ in range(K):
        now = A[now]
    print(now+1)




    



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split(" "))
A = list(map(int,input().split(" ")))
A.insert(0,0)
rireki = [1]
counter = 1
now = 1
flag = [0 for _ in range(N + 1)]
flag[1] = 1
while(flag[A[now]] == 0):
    counter += 1
    rireki.append(A[now])
    flag[A[now]] = counter
    now = A[now]
if K < flag[A[now]]:
    print(rireki[K - 1])
else:
    K -= flag[A[now]] - 1
    K %= counter - flag[A[now]] + 1
    print(rireki[flag[A[now]] + K - 1])

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = [int(e) for e in input().split()]

next_map = {}

for i, e in enumerate(A):
    next_map[i+1] = e


history = ""
here = 1
p_i = 0
unit_length = 0
history += str(here)

for i in range(N):
    here = next_map[here]
    if str(here) in history:
        p_i = history.index(str(here))
        n_i = i
        unit_length = n_i - p_i + 1
        break
    history += str(here)


if K < p_i:
    print(history[K])
else:
    print(history[p_i + (K-p_i) % unit_length])

Submission status: Wrong Answer

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

init = [1]
while True:
    nxt = a[init[-1]-1]
    if nxt in init:
        idx_nxt = init.index(nxt)
        loop = init[idx_nxt:]
        init = init[:idx_nxt]
        break
    else:
        init.append(nxt)

idx = (k-len(init))%len(loop)
print(loop[idx])

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    def int_0(num):
        return int(num) - 1

    N, K = map(int, input().split())
    A = tuple(map(int_0, input().split()))
    
    # dfs
    INF = 10 ** 18
    visited = [False] * N
    dist = [INF] * N
    info  = {}
    def dfs(s):
        stack = deque()
        stack.append(s)
        visited[s] = True
        dist[s] = 0
        while stack:
            now = stack.pop()
            visited[now] = True
            nv = A[now]
            if visited[nv] == True:
                info["start"] = nv
                info["length"] = dist[now] - dist[nv] + 1
                info["f"] = dist[nv]
                break
            else:
                dist[nv] = dist[now] + 1
                stack.append(nv)
    dfs(0)

    if K <= N:
        now = 0
        for _ in range(K):
            now = A[now]
        print(now)

    K -= info["f"]
    K %= info["length"]

    now = info["start"]
    for _ in range(K):
        now = A[now]
    print(now+1)




    



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque
import heapq
import itertools
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(x, cnt):
  if visited[x-1] != -1:
    return [visited[x-1], cnt-visited[x-1]]
  else:
    visited[x-1] = cnt
    return tami(a[x-1], cnt+1)

def nasu1(x, cnt):
  if cnt == start:
    return x
  else:
    return nasu1(a[x-1], cnt+1)

def nasu2(x, cnt):
  if cnt == start + num:
    return x
  else:
    return nasu2(a[x-1], cnt+1)

N,K = IL()
a = IL()

visited = [-1]*N
start, roop = tami(1, 0)
if K <= start:
  print(nasu1(1, 0))
else:
  #print(visited)
  num = (K-start)%roop
  #print(start,roop,num)

  print(nasu2(1, 0))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)


def read():
    N, K = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, K, A


def solve(N, K, A, INF = 10**8):
    counts = [0 for i in range(N)]
    a = 1
    loop_init = -1
    loop_count = -1
    while True:
        counts[a-1] += 1
        if counts[a-1] == 2 and loop_count < 0:
            loop_count = 0
        elif counts[a-1] == 3:
            loop_count += 1
            break
        elif loop_count >= 0:
            loop_count += 1
        a = A[a-1]
    loop_init = sum([c == 1 for c in counts])

    loop_k = (K - loop_init) % loop_count

    a = 1
    for i in range(loop_init + loop_k):
        a = A[a-1]
    return a


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Wrong Answer

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *					# ll = deepcopy(l)
from heapq import *					# heappush(hp,x)
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize				# minn = -maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *				# pre = [0] + list(accumulate(l))
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''
4 5
3 2 4 1
'''

def solve(l,k):
	n = len(l)
	curr = 0
	zz = 1
	done = defaultdict(int)
	last = 1
	prev = 0
	done[curr+1] = zz
	while(zz <= k):
		prev = curr
		curr = l[curr]-1
		zz += 1
		if(done[curr+1] != 0):
			last = curr+1
			break
		else:
			done[curr+1] = zz
	if(len(done) == 1):
		return l[0]
	zz -= 1
	mod = k%zz
	k = k - done[last] + 1
	cycle = zz - done[last] + 1
	mod = k%cycle
	find = mod+done[last]
	for i in done:
		if(done[i] == find):
			return i
	return curr+1
	

N,K = list(map(int, stdin.readline().rstrip().split()))
l = list(map(int, stdin.readline().rstrip().split()))
ans = solve(l,K)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n,k=map(int, input().split())
A=[int(i)-1 for i in input().split()]
now=0
loop=[]
dd = defaultdict(int)

while k!=0:
    k-=1
    now = A[now]
    if dd[now]>0:
        break
    else:
        dd[now]+=1
    if k==0:
        print(now)
        exit()
    loop.append(now)

l=(abs(loop.index(now)-len(loop)))#ループの長さ
t = loop.index(now)#ループの開始index
print(loop[t+k%(l-t)]+1)

Submission status: Wrong Answer

Solution code:




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


cnt_place = [0] * N
nxt = 1
cnt = 0
loop_cnt = 0
visited = [False] * N

first =  [0] * N
if A[0] == 1:
    print(1)
    exit()
else:
    while True:

        if visited[nxt-1]:
            
            break

       
        cnt_place[cnt] = nxt
        visited[nxt-1] = True
        first[nxt-1] = cnt
        
        cnt += 1
        nxt = A[nxt-1]
        

    if K <= cnt:
        print(cnt_place[K+1])
    else:
        
        K -= first[nxt-1]
        num = K % (cnt - first[nxt-1])
        print(cnt_place[num + first[nxt-1]])

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest


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

    loop_list = []
    now = 0

    while 1:
        now = a[now] - 1

        if now + 1 in set(loop_list):
            s_index = loop_list.index(now + 1)
            before_loop = s_index
            loop_list = loop_list[s_index:]
            break
        else:
            loop_list.append(now + 1)

    l = len(loop_list)
    k -= before_loop

    # print(loop_list, l, before_loop)
    print(loop_list[k % l - 1])




class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4 5
3 2 4 1"""
        output = """4"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """6 727202214173249351
6 5 2 5 3 2"""
        output = """2"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Wrong Answer

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

if k <= n:
    takahashi = 0
    for _ in range(k):
        takahashi = a[takahashi] - 1
    print(takahashi + 1)
else:
    start = 0
    takahashi = start
    trajectory = [takahashi]
    for i in range(n):
        takahashi = a[takahashi] - 1
        if takahashi == start:
            break
        trajectory.append(takahashi)
    print(trajectory[k % (i + 1)] + 1)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
B = []
for i in range(len(A)):
    B.append(0)

ok = 0
i = 0
cnt1 = 0
cnt2 = 0
B[0] = 1
while ok == 0:
    i = A[i]-1
    if B[i] == 0:
        B[i] = 1
    else:
        ok = 1
        B[i] = 2
    cnt1 += 1

while ok == 1:
    i = A[i]-1
    if B[i] == 1:
        B[i] = 2
    else:
        ok = 2
    cnt2 += 1

if K > cnt1:
    K -= cnt1
if K > cnt2:
    K = K % cnt2

while K > 0:
    i = A[i]-1
    K -= 1

print(i+1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

N, K = read_ints()

A = read_ints()
B = []
for a in A:
    B.append(a - 1)

# ループするまで回してみる?
# 閉路が知りたい
# 閉路の起点をメモ
# K←（K-起点までの回数）
# K%閉路の長さ
# のこりは愚直に起点から再スタート

nums_to_arrive = [-1] * N
nums_to_arrive[0] = 0
now = 0
while True:
    to = B[now]
    if nums_to_arrive[to] == -1:
        nums_to_arrive[to] = nums_to_arrive[now] + 1
        # if nums_to_arrive[to] == K:
        #     print(to)
        #     exit()
    else:
        break
    now = to
n1 = nums_to_arrive[to]
n2 = nums_to_arrive[now] + 1 - n1
base = to  # 起点
# print(base)


K = (K - n1) % n2  # 残り移動回数
# print(K)
now = base  # 起点をもとに開始する
while K:
    to = B[now]
    K -= 1
    now = to
print(now + 1)
# print(to + 1)

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline().rstrip('\n')


def calc(N, K, A):
    n = 1
    k = 0
    d = {n: k}
    while True:
        k += 1
        n = A[n - 1]
        if not n in d:
            d[n] = k
        else:
            x = (K - d[n] + 1) % (k - d[n])
            for i in d:
                if d[n] - 1 + x == d[i]:
                    return i

    

(N, K) = tuple([int(s) for s in input().split()])
A = [int(s) for s in input().split()]
print(calc(N, K, A))

Submission status: Wrong Answer

Solution code:
def calc(i, k):
    ans_list = [i]
    count = 1
    i = a[i]
    while i not in ans_list:
        ans_list.append(i)
        count += 1
        i = a[i]
    index = ans_list.index(i)
    ans_list.append(i)
    return count, ans_list

n, k = map(int, input().split())
a = [int(i) - 1 for i in input().split()]

count, ans_list = calc(0, k)

index = ans_list.index(ans_list[-1])
k = k - index
ans_list = ans_list[index + 1:]
print(ans_list[k % len(ans_list) - 1] + 1)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [1,a[0]]
sircle=[]
not_sircle = []
i = 0
while True:
    i=a[i]-1
    b.append(a[i])
    if a[i] in b[0:-1]:
        not_sircle = b[0:b.index(a[i])]
        sircle = b[b.index(a[i]):-1]
        break
mod = (k-len(not_sircle))%len(sircle)
if len(not_sircle)>=k:
    print(not_sircle[k-1])
else:
    print(sircle[mod])

Submission status: Wrong Answer

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, K = lr()
    A = lr()
    vis = [-1]*(N+1)
    dis = [0]*(N+1)
    v = 1
    cnt = 0
    while vis[v] == -1:
        dis[cnt] = v
        vis[v] = cnt
        v = A[v-1]
        cnt += 1
    print(dis[(K-vis[v])%(cnt-vis[v])+vis[v]])
resolve()

Submission status: Wrong Answer

Solution code:
"""
N towns
teleporter each town
teleporter at town i -> town A_i
k-times teleporter after starting at town 1
"""

from collections import deque

n, k = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))

visited = [0] * n
path = deque()
cur = 0

while not visited[cur]:
    visited[cur] = 1
    path.append(cur)
    cur = a[cur]

while path[0] != cur:
    k -= 1
    path.popleft()

#print(path)
print((path[k % len(path)]) + 1)

Submission status: Wrong Answer

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

t = K%N

for i in range(t):
    if i==0:
  	    k = A[A[N-1]-1]
    else:
        k = A[k-1]
print(A[k-1])

Submission status: Wrong Answer

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

ans=[]

j=0 #A進み
while A[j] not in ans:
    ans.append(A[j])
    j=A[j]-1
ans.append(A[j])

st=ans.index(A[j])
ans=ans[st:-1]
K-=st
l=len(ans)
#print(ans)
print(ans[K%l-1])

Submission status: Wrong Answer

Solution code:
import math,sys
from sys import stdin, stdout
from collections import Counter, defaultdict, deque
input = stdin.readline
I = lambda:int(input())
li = lambda:list(map(int,input().split()))

def case():
    n,k=li()
    a=li()
    d=defaultdict(int)
    i=0
    d[1]=1
    c=0
    ans=[1]
    while(a[i] not in d):
        d[a[i]]=1
        c+=1 
        ans.append(a[i])
        i=a[i]-1
    print(ans)
   # print(i)
    if(k<len(a)):
        print(ans[k%len(ans)])
        return
    for j in range(len(ans)):
        if(ans[j]==a[i]):
            ans=ans[j:]
            k-=j
            break 

    #print(ans,k)
    print(ans[(k)%len(ans)])
    




for _ in range(1):
    case()

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
"""
閉路をmodを取って出力
閉路になっていない(回帰するなら)ならそこを出力
"""
n,k = map(int,readline().split())
lst1 = list(map(int,readline().split()))


visited = [-1]*n #modを取った時にそこにたどり着く
visited[0] = 0
now = 0
count = 1
mod = -1
lim = -1
while True:
    now = lst1[now] -1
    if visited[now] != -1: #閉路
        mod = count - visited[now]
        lim = visited[now]
        break
    if now == lst1[now]-1: #回帰
        lim = now
        visited[now] = -51
        mod = 0
        break
    visited[now] = count

    count += 1
    
if k <= lim:
    for i in range(n):
        if visited[i] == k:
            print(i+1)
            exit()
else:
    if mod == 0:
        for i in range(n):
            if visited[i] == -51:
                print(i+1)
                exit() 
    else:
        res = (k-lim)%mod
        for i in range(n):
            if visited[i]-lim == res:
                print(i+1)
                exit()

Submission status: Wrong Answer

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

counter=1
now=1
gone_set={1}
gone_list=[1]
place=1
while counter<=N:
    next=A[now]
    if next in gone_set:
        start=gone_list.index(next)
        loop=len(gone_list)-start
        last=(K-start)%loop
        place=gone_list[start+last]
        break
    else:
        gone_set.add(next)
        gone_list.append(next)
        now=next
        counter+=1

print(place)