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: Runtime Error

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

current = 0
d = dict()
d[current] = d.get(current, 0) + 1
pattern = [0]
cnt = K

while True:
    current = A[current]
    if d.get(current) == 2:
        break
    else:
        if d.get(current) == None:
            d[current] = d.get(current, 0) + 1
        else:
            d[current] = d.get(current) + 1
        pattern.append(current)
        cnt -= 1
        if cnt == 0:
            break
if cnt == 0:
    print(pattern[-1]+1)
else:
    loop = [key for key, value in d.items() if value == 2]
    res = len(pattern) % ((len(loop)) // 2)
    ans = (K - res) % len(loop)

    print(pattern[res+ans]+1)

Submission status: Runtime Error

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

for i in range(0,K):
    b=a[c]
    c=a[b]

print(b)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
def main():
    N, K = map(int, input().split())
    A = [int(x) - 1 for x in input().split()]

    way = []
    now = 0
    for _ in range(K):
        if now in way:
            loop_start = way.index(now)
            loop = way[loop_start:]
            K -= len(way[:loop_start])
            now = loop[K - len(way[:loop_start]) % len(loop)]
            break
        way.append(now)
        now = A[now]
    print(now + 1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
def main():
    N, K = map(int, input().split())
    A = [int(x) - 1 for x in input().split()]

    route = []
    now = 0
    for k in range(K):
        if now in route:
            break
        route.append(now)
        now = A[now]

    loop_start = route.index(now)
    K -= len(route[:loop_start])
    K %= len(route[loop_start:])
    for k in range(K):
        now = A[now]
    print(now + 1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
B = [0];BB=[0]
S = set([]);S.add(0)
now = 0
Flag = False
loop_start = -1
if K <= 2*pow(10,5)+10:
  for i in range(K):
    nxt = A[now]-1
    BB.append(nxt)
    now = nxt
  #print(BB)
  print(BB[K]+1)
  exit()
for i in range(N*2):
  nxt = A[now]-1
  #print(now,nxt)
  if nxt in S:
    if Flag:
      if nxt == loop_start:
        #print(nxt,i)
        loop_cycle = i-loop_num
        break
    else:
      loop_start = nxt
      loop_num = i
      Flag = True
  else:
    B.append(nxt);S.add(nxt)
  now = nxt
#print(B,loop_start,loop_cycle,loop_num)
loc = (K-loop_start)%loop_cycle+loop_num
#print(loc)
#print(len(B))
print(B[loc]+1)

Submission status: Runtime Error

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
B = [0]
S = set([]);S.add(0)
now = 0
Flag = False
loop_start = -1
if K <= 2*pow(10,5)+10:
  for i in range(K):
    nxt = A[now]-1
    B.append(nxt)
    now = nxt
  #print(B)
  print(B[K]+1)
  exit()
for i in range(N*2):
  nxt = A[now]-1
  #print(now,nxt)
  if nxt in S:
    if Flag:
      if nxt == loop_start:
        #print(nxt,i)
        loop_cycle = i-loop_num
        break
    else:
      loop_start = nxt
      loop_num = i
      Flag = True
  else:
    B.append(nxt);S.add(nxt)
  now = nxt
#print(B,loop_start,loop_cycle,loop_num)
loc = (K-loop_start)%loop_cycle+loop_start
#print(loc)
print(B[loc]+1)

Submission status: Runtime Error

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
B = [0]
S = set([]);S.add(0)
now = 0
Flag = False
loop_start = -1
if K <= 2*pow(10,5)+10:
  for i in range(K):
    nxt = A[now]-1
    B.append(nxt)
    now = nxt
  #print(B)
  print(B[K]+1)
  exit()
for i in range(K*2):
  nxt = A[now]-1
  #print(now,nxt)
  if nxt in S:
    if Flag:
      if nxt == loop_start:
        #print(nxt,i)
        loop_cycle = i-loop_num
        break
    else:
      loop_start = nxt
      loop_num = i
      Flag = True
  else:
    B.append(nxt);S.add(nxt)
  now = nxt
#print(B,loop_start,loop_cycle,loop_num)
loc = (K-loop_start)%loop_cycle+loop_start
#print(loc)
print(B[loc]+1)

Submission status: Runtime Error

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
B = [0]
S = set([]);S.add(0)
now = 0
Flag = False
loop_start = -1
if K <= 2*pow(10,5)+10:
  for i in range(K):
    nxt = A[now]-1
    B.append(nxt)
    now = nxt
  print(B)
  print(B[K]+1)
  exit()
for i in range(K):
  nxt = A[now]-1
  #print(now,nxt)
  if nxt in S:
    if Flag:
      if nxt == loop_start:
        #print(nxt,i)
        loop_cycle = i-loop_num
        break
    else:
      loop_start = nxt
      loop_num = i
      Flag = True
  else:
    B.append(nxt);S.add(nxt)
  now = nxt
#print(B,loop_start,loop_cycle,loop_num)
loc = (K-loop_start)%loop_cycle+loop_start
#print(loc)
print(B[loc]+1)

Submission status: Runtime Error

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

cnt = 0
cl = [-1]*(n+1)
cll = [1]
curr = 1
for i in range(min(n,k)):
    # print(curr)
    next_c = al[curr-1]
    if cl[next_c] != -1:
        # loop_start = (i+1)
        loop_start = cl[next_c]
        rem = k - (i+1)
        break
    else:
        cl[next_c] = i + 1
        cll.append(next_c)
    curr = next_c

else:
    print(curr)

# print(rem)
loop_c = cll[loop_start:]
# print(loop_c)
last_ind = rem%len(loop_c)
ans = loop_c[last_ind]
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
ind = 0
l = []
for i in range(k):
    if ind in l:
        break
    l.append(ind)
    ind = a[ind]-1
l = l[l.index(ind):]
for i in range((k-i)%len(l)):
    ind = a[ind]-1
print(ind+1)

Submission status: Runtime Error

Solution code:
from sys import stdin,stdout
from collections import defaultdict
def dfs1(src):
    global steps
    if steps==rem:return src
    steps+=1
    return dfs1(g[src][0])
def dfs(src):
    global steps,done,boc,nic
    vis[src]=1
    steps+=1
    dfn[src]=steps
    for neigh in g[src]:
        if not vis[neigh]:dfs(neigh)
        else:
            boc,done,nic=[neigh,steps,steps-dfn[neigh]+1]
            # print(done,boc,nic)
            return

n,k=list(map(int,stdin.readline().split()))
done,boc,nic=0,0,0
a=list(map(int,stdin.readline().split()))
g=defaultdict(list)
for i in range(1,n+1):
    g[i]+=[a[i-1]]
vis=[0]*(n+1)
dfn=[0]*(1+n)
steps=0
dfs(1)
# print(done,boc,nic)
left=k-done
rem=(left%nic)
if rem==0:rem=nic
steps=1
print(dfs1(g[boc][0]))

Submission status: Runtime Error

Solution code:
from sys import stdin,stdout
from collections import defaultdict
def dfs1(src):
    global steps
    if steps>rem:return src
    steps+=1
    return dfs1(g[src][0])
def dfs(src):
    global steps,done,boc,nic
    vis[src]=1
    steps+=1
    dfn[src]=steps
    for neigh in g[src]:
        if not vis[neigh]:dfs(neigh)
        else:
            boc,done,nic=[neigh,steps,steps-dfn[neigh]+1]
            # print(done,boc,nic)
            return

n,k=list(map(int,stdin.readline().split()))
done,boc,nic=0,0,0
a=list(map(int,stdin.readline().split()))
g=defaultdict(list)
for i in range(1,n+1):
    g[i]+=[a[i-1]]
vis=[0]*(n+1)
dfn=[0]*(1+n)
steps=0
dfs(1)
# print(done,boc,nic)
left=k-done
rem=(left%nic)
if rem==0:rem=nic
steps=1
print(dfs1(boc))

Submission status: Runtime Error

Solution code:
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
a = [aa-1 for aa in a]
check = [0 for i in range(n)]

count = 0
point = 0
check[0] = 1
path = [0]
for i in range(min(n, k)):
    if i == 0 or check[point] == 0:
        check[point] = 1
        point = a[point]
        path.append(point)
    else:
        break

for i in range(len(path)):
    if path[i] == point:
        break
    else:
        count += 1

k -= count
p = k % (len(path)-count-1)

for i in range(p):
    point = a[point]
  
print(point+1)

Submission status: Runtime Error

Solution code:
import heapq

def binary_search(data, value):
    left = 0            # 探索する範囲の左端を設定
    right = len(data) - 1            # 探索する範囲の右端を設定
    while left <= right:
        mid = (left + right) // 2            # 探索する範囲の中央を計算
        if data[mid] == value:
            # 中央の値と一致した場合は位置を返す
            return mid
        elif data[mid] < value:
            # 中央の値より大きい場合は探索範囲の左を変える
            left = mid + 1
        else:
            # 中央の値より小さい場合は探索範囲の右を変える
            right = mid - 1
    return -1            # 見つからなかった場合

n, k = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
way = [0]
hq = [0]
heapq.heapify(hq)
posi = 0
cycle = 0
while True:
    if binary_search(hq, a[posi]) != -1:
        rest = way.index(a[posi])
        cycle -= (rest - 1)
        break
    way.append(a[posi])
    heapq.heappush(hq, a[posi])
    posi = a[posi]
    cycle += 1
# print(way)
# print(cycle)
if k < len[way]:
    print(way[k])
else:
    print(way[(k-rest) % cycle + rest] + 1)

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

class Roop:
    def __init__(self, array):
        self.n = len(array)
        self.array = array
        # ループ検出
        self.roops = []
        # iはどのループのものか
        self.roop_dict = [-2] * self.n
        # ループ内の何番目にあるか
        self.opt_dic = [-1] * self.n
        ignore = [-1] * self.n
        cnt = 0
        for i in range(self.n):
            if ignore[i] >= 0:
                continue
            opt = [i]
            # opt内の何番目にあるか
            self.opt_dic[i] = 0
            c = 1
            # 探索したらフラグを立てる
            ignore[i] = 1
            # i → array[i]
            to = array[i]
            # ループが詰まるまで回す
            while True:
                if ignore[to] >= 0:
                    # 既にループ作成済なら
                    if self.roop_dict[to] >= -1:
                        break
                    # tail部分については-1に
                    for j in range(self.opt_dic[to]):
                        self.roop_dict[opt[j]] = -1
                    # 作成してないならループ作成
                    for j in range(self.opt_dic[to], len(opt)):
                        self.roop_dict[opt[j]] = cnt
                    self.roops.append(opt[self.opt_dic[to]:])
                    # 次のループはcnt + 1番
                    cnt += 1
                    break
                opt.append(to)
                ignore[to] = 1
                self.opt_dic[to] = c
                c += 1
                to = array[to]

    # xがどの番号のループにあるか
    def roop_n(self, x):
        if self.roop_dict[x] == float('inf'):
            return -1
        return self.roop_dict[x]

    # xが入っているループは何か
    # ループ内になければFalse
    def inspect(self, x):
        if self.roop_n(x) == -1:
            return False
        return self.roops[self.roop_dict(x)]

    # ループの大きさ
    def roop_len(self, x):
        return len(self.roops[self.roop_n(x)])

    # xからk回移動してどの場所に行けるか
    def move(self, x, k):
        cnt = k
        to = x
        # ループに入る前にどのルートを通ったか
        # スタート地点から既にループに入っていた場合、headは空になる
        head = []
        # ループ脱出後どのルートを通るか
        tail = []
        # 何回ループしたか
        time = -1
        res = 0
        while cnt > 0:
            to = self.array[to]
            cnt -= 1
            # まだループしておらず、踏んだ場所がループ内にある場合
            if time == -1 and self.roop_n(to) >= 0:
                r = self.roops[self.roop_n(to)]
                time = (cnt // len(r))
                cnt -= time * len(r)
            # ループ前なら
            if time == -1:
                head.append(to)
            # ループ後なら
            else:
                tail.append(to)
        # 例: N, K = 6 727202214173249351
        # A = [6, 5, 2, 5, 3, 2]の時
        # 1回目の移動 1 → 6
        # 2回目の移動 6 → ### ここからループが始まる ### → 2
        # ... 242400738057749783回ループ
        # 727202214173249351回目の移動 3 → 2
        # to, head, tail, time = (1, [5], [1], 242400738057749783)
        return to

"""
N, A = getNM()
A -= 1
K = getN()
B = [i - 1 for i in getList()]
roop = Roop(B)
print(roop.roops)
print(roop.move(A, K) + 1)

"""
# ABC167 D - Teleporter
N, K = getNM()
N -= 1
A = [i - 1 for i in getList()]
roop = Roop(A)
print(roop.move(0, K) + 1)



"""
# ABC175 D - Moving Piece
N, K = getNM()
P = [i - 1 for i in getList()]
C = getList()
# ループ検出
roop = Roop(P)

# 各ループごと調べる
ans = -float('inf')
for r in roop.roops:
    n = len(r)
    # ループに対応するスコアリストを用意
    alta = []
    for i in range(n):
        alta.append(C[r[i]])
    # １回ループすると何点getできるか
    one_roop = sum(alta)
    alta += alta
    imos = [0]
    for i in range(len(alta)):
        imos.append(imos[i] + alta[i])

    t = min(n, K)
    for i in range(n):
        # 長さ1からtまでの区間の総和の最大値を探索
        for j in range(1, t + 1):
            if one_roop >= 0:
                opt = (imos[i + j] - imos[i]) + ((K - j) // n) * one_roop
            else:
                opt = imos[i + j] - imos[i]
            ans = max(ans, opt)

print(ans)
"""

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

class Roop:
    def __init__(self, array):
        self.n = len(array)
        self.array = array
        # ループ検出
        self.roops = []
        # iはどのループのものか
        self.roop_dict = [-1] * self.n
        # ループ内の何番目にあるか
        self.opt_dic = [-1] * self.n
        ignore = [-1] * self.n
        cnt = 0
        for i in range(self.n):
            if ignore[i] >= 0:
                continue
            opt = [i]
            # opt内の何番目にあるか
            self.opt_dic[i] = 0
            c = 1
            # 探索したらフラグを立てる
            ignore[i] = 1
            # i → array[i]
            to = array[i]
            # ループが詰まるまで回す
            while True:
                if ignore[to] >= 0:
                    # 既にループ作成済なら
                    if self.roop_dict[to] >= 0:
                        break
                    # tail部分についてはfloat('inf')に
                    for j in range(self.opt_dic[to]):
                        self.roop_dict[opt[j]] = float('inf')
                    # 作成してないならループ作成
                    for j in range(self.opt_dic[to], len(opt)):
                        self.roop_dict[opt[j]] = cnt
                    self.roops.append(opt[self.opt_dic[to]:])
                    # 次のループはcnt + 1番
                    cnt += 1
                    break
                opt.append(to)
                ignore[to] = 1
                self.opt_dic[to] = c
                c += 1
                to = array[to]

    # xがどの番号のループにあるか
    def roop_n(self, x):
        if self.roop_dict[x] == float('inf'):
            return -1
        return self.roop_dict[x]

    # xが入っているループは何か
    # ループ内になければFalse
    def inspect(self, x):
        if self.roop_n(x) == -1:
            return False
        return self.roops[self.roop_dict(x)]

    # ループの大きさ
    def roop_len(self, x):
        return len(self.roops[self.roop_n(x)])

    # xからk回移動してどの場所に行けるか
    def move(self, x, k):
        cnt = k
        to = x
        # ループに入る前にどのルートを通ったか
        # スタート地点から既にループに入っていた場合、headは空になる
        head = []
        # ループ脱出後どのルートを通るか
        tail = []
        # 何回ループしたか
        time = -1
        res = 0
        while cnt > 0:
            to = self.array[to]
            cnt -= 1
            # まだループしておらず、踏んだ場所がループ内にある場合
            if time == -1 and self.roop_n(to) >= 0:
                r = self.roops[self.roop_n(to)]
                time = (cnt // len(r))
                cnt -= time * len(r)
            # ループ前なら
            if time == -1:
                head.append(to)
            # ループ後なら
            else:
                tail.append(to)
        # 例: N, K = 6 727202214173249351
        # A = [6, 5, 2, 5, 3, 2]の時
        # 1回目の移動 1 → 6
        # 2回目の移動 6 → ### ここからループが始まる ### → 2
        # ... 242400738057749783回ループ
        # 727202214173249351回目の移動 3 → 2
        # to, head, tail, time = (1, [5], [1], 242400738057749783)
        return to

"""
N, A = getNM()
A -= 1
K = getN()
B = [i - 1 for i in getList()]
roop = Roop(B)
print(roop.roops)
print(roop.move(A, K) + 1)

"""
# ABC167 D - Teleporter
N, K = getNM()
N -= 1
A = [i - 1 for i in getList()]
roop = Roop(A)
print(roop.move(0, K) + 1)

"""
# ABC175 D - Moving Piece
N, K = getNM()
P = [i - 1 for i in getList()]
C = getList()
# ループ検出
roop = Roop(P)

# 各ループごと調べる
ans = -float('inf')
for r in roop.roops:
    n = len(r)
    # ループに対応するスコアリストを用意
    alta = []
    for i in range(n):
        alta.append(C[r[i]])
    # １回ループすると何点getできるか
    one_roop = sum(alta)
    alta += alta
    imos = [0]
    for i in range(len(alta)):
        imos.append(imos[i] + alta[i])

    t = min(n, K)
    for i in range(n):
        # 長さ1からtまでの区間の総和の最大値を探索
        for j in range(1, t + 1):
            if one_roop >= 0:
                opt = (imos[i + j] - imos[i]) + ((K - j) // n) * one_roop
            else:
                opt = imos[i + j] - imos[i]
            ans = max(ans, opt)

print(ans)
"""

Submission status: Runtime Error

Solution code:
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
sys.setrecursionlimit(500*500)
import itertools
from collections import Counter,deque

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

    c = []
    mark = [-1]*n
    pos,l = 0,0
    while 1:
        if mark[pos] >= 0:
            l = mark[pos]
            break
        mark[pos] = len(c)
        c.append(pos)
        pos = a[pos] - 1
    if k <= l:
        print(c[k] + 1)
    else:
        k -= l
        print(c[l + k%(len(c) - 1)] + 1)
if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
sys.setrecursionlimit(500*500)
import itertools
from collections import Counter,deque

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

    c = []
    mark = [-1]*n
    pos,l = 0,0
    while 1:
        if mark[pos] >= 0:
            l = mark[pos]
            break
        mark[pos] = len(c)
        c.append(pos)
        pos = a[pos] - 1
    if k <= 1:
        print(c[k] + 1)
    else:
        k -= l
        print(c[l + k%(len(c) - 1)] + 1)
if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter
n, k = map(int, input().split())
A = list(map(int, input().split()))
C = Counter([])
X, Y = [], []
m = 0
for _ in range(n):
    a = A[m]-1
    C[m] += 1
    X.append(m)
    if C[a] != 0:
        Y = X[X.index(a):]
        X = X[:X.index(a)]
        break
    m = a
# print(X,Y)
x = len(X)
y = len(Y)
if k-1 <= x:
    print(X[k]+1)
else:
    k -= x
    print(Y[k-(k//y)*y]+1)

Submission status: Runtime Error

Solution code:
from collections import Counter
n, k = map(int, input().split())
A = list(map(int, input().split()))
C = Counter([])
X, Y = [], []
m = 0
for _ in range(n):
    a = A[m]-1
    C[m] += 1
    X.append(m)
    if C[a] != 0:
        Y = X[X.index(a):]
        X = X[:X.index(a)]
        break
    m = a
# print(X,Y)
x=len(X)
y=len(Y)
if k <= x:
    print(X[k]+1)
else:
    k -= x
    print(Y[k-(k//y)*y]+1)

Submission status: Runtime Error

Solution code:
import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))
d=np.array(1)
initial=0
for i in range(N):
	if A[initial] in d:
		loop=d.shape[0]-np.where(d==A[initial])[0][0]
		break
	else:	
		d=np.append(d,A[initial])
		initial=A[initial]-1
#print(loop)
mod=int((K-np.where(d==A[initial])[0][0])%loop)
#print(mod)
print(d[np.where(d==A[initial])[0][0]+mod])

Submission status: Runtime Error

Solution code:
from collections import Counter
N, K = map(int,input().split())
A = list(map(int,input().split()))
i = k = 0
B = [1]
for i in range(N):
    B.append(A[B[i]])
S = Counter(B)
idx = S.most_common(1)[0][0]
i = k = cnt = 0
k_s = None
while k < 10 ** 6:
    if B[k] == idx and cnt == 1:
        k_s = k
        break
    elif B[k] == idx:
        k_f = k
        cnt += 1
    k += 1
if k_s:
    k_max = K % (k_s - k_f)
else:
    k_max = K
i = k = 0
while k < k_max:
    i = A[i] - 1
    k += 1
print(i + 1)

Submission status: Runtime Error

Solution code:
from collections import Counter
N, K = map(int,input().split())
A = list(map(int,input().split()))
i = k = 0
B = [1]
for i in range(n):
    B.append(A[B[i]])
S = Counter(B)
idx = S.most_common(1)[0][0]
i = k = cnt = 0
k_s = None
while k < 10 ** 6:
    if B[k] == idx and cnt == 1:
        k_s = k
        break
    elif B[k] == idx:
        k_f = k
        cnt += 1
    k += 1
if k_s:
    k_max = K % (k_s - k_f)
else:
    k_max = K
i = k = 0
while k < k_max:
    i = A[i] - 1
    k += 1
print(i + 1)

Submission status: Runtime Error

Solution code:
from collections import Counter
N, K = map(int,input().split())
A = list(map(int,input().split()))
i = k = 0
B = [1]
while k <= N or k <= K:
    i = A[i] - 1
    B.append(i + 1)
    k += 1
S = Counter(B)
idx = S.most_common(1)[0][0]
i = k = cnt = 0
while k < 10 ** 6:
    if B[k] == idx and cnt == 1:
        k_s = k
        break
    elif B[k] == idx:
        k_f = k
    k += 1
if k_s:
    k_max = K % (k_s - k_f)
else:
    k_max = K
i = k = 0
while k < k_max:
    i = A[i] - 1
    k += 1
print(i + 1)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
ls = list(map(int,input().split()))
di = [1]
fi = [-1]*(n+1)
a = 0
for i in range(k):
    if fi[ls[a]] == -1:
        fi[ls[a]] = i
        a = ls[a] - 1
    else:
        ind = fi[ls[a]]
        t = (k - ind) % (max(fi) - ind)
        t += ind
        print(fi.index(t))
        break
else:
    print(a)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
ls = list(map(int,input().split()))
di = [1]
fi = [0]*(n+1)
a = 0
for i in range(k):
    if fi[ls[a]] == 0:
        fi[ls[a]] = i
        a = ls[a] - 1
    else:
        ind = fi[ls[a]]
        t = (k - ind) % (max(fi) - ind)
        t += ind
        print(fi.index(t))
        break
else:
    print(a)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
ls = list(map(int,input().split()))
di = [1]
fi = [0]*(n+1)
a = 0
for i in range(k+1):
    if fi[ls[a]] == 0:
        fi[ls[a]] = i
        a = ls[a] - 1
    else:
        ind = fi[ls[a]]
        t = (k - ind) % (max(fi) - ind)
        t += ind
        print(fi.index(t))
        break
else:
    print(a)

Submission status: Runtime Error

Solution code:
import bisect,collections,copy,heapq,itertools,math,string
from collections import defaultdict as D
from functools import reduce
import numpy as np
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")

# k: number of transfer
_,k = LI()
a = LI()
# 街の番号を0始まりに変更
a = list(map(lambda x:x-1,a))
# print(a)

_s = set([0])

# 再帰関数
def rec(visited,next,s):
    if next in s:
        # print(visited)
        return visited,visited.index(next)
    else:
        s.add(next)
        visited.append(next)
        return rec(visited,a[next],s)

visited = [0]
# 訪れた街、初めて2度訪れた街のインデックスを取得
visited,loopStart = rec(visited,a[0],_s)

# print(visited,loopStart)

if k <= len(visited):
    townIndex = visited[k]
else:
    visitedLoop = visited[loopStart:]
    # print(visitedLoop)
    # 残り回数を循環配列の長さで割った余り
    index = (k-(loopStart))%len(visitedLoop)
    # print(index)
    townIndex = visitedLoop[index]

print(townIndex+1)

Submission status: Runtime Error

Solution code:
import bisect,collections,copy,heapq,itertools,math,string
from collections import defaultdict as D
from functools import reduce
import numpy as np
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")

# k: number of transfer
_,k = LI()
a = LI()
# 街の番号を0始まりに変更
a = list(map(lambda x:x-1,a))
# print(a)

s = set([0])
# 再帰関数
def rec(visited,next):
    if next in s:
        return visited,visited.index(next)
    else:
        s.add(next)
        visited.append(next)
        return rec(visited,a[next])

visited = [0]
# 訪れた街、初めて2度訪れた街のインデックスを取得
visited,loopStart = rec(visited,a[0])

# print(visited,loopStart)

if k <= len(visited):
    townIndex = visited[k]
else:
    visitedLoop = visited[loopStart:]
    # print(visitedLoop)
    # 残り回数を循環配列の長さで割った余り
    index = (k-(loopStart))%len(visitedLoop)
    # print(index)
    townIndex = visitedLoop[index]

print(townIndex+1)

Submission status: Runtime Error

Solution code:
N,K = map(int, input().split())
data = list(map(int, input().split()))
town = [0] * N
temp = []
once = []



p = 1 #pointer
for i in range(N):
  temp.append(p-1)
  if town[p-1] == 1:
    break
  else:
    town[p-1] = 1
    p = data[p-1]
    #print(town)
    #print("pointer = {}".format(p))

#print(temp)

while True:
  if temp[0] == temp[-1]:
    break
  else:
    once.append(temp[0])
    temp.pop(0)


temp.pop(-1)
#print(once)
#print(temp)

if K <= len(once):
  print(once[K] + 1)
else :
  K = K - len(once)
  K = K % len(temp)
  print(temp[K]+1)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
top = -1
hist = []
finished = [True] + [False for _ in range(N)]
seen = [True] + [False for _ in range(N)]

def dfs(cur):
    global hist, finished, seen, top
    hist.append(cur)
    seen[cur] = True
    nex = A[cur]
    if seen[nex] and not finished[nex]:
        top = nex
        return
    dfs(nex)
    if not top == -1:
        return
    hist.pop()
    finished[cur] = True
    
dfs(1)
cycle = []
while not hist == []:
    i = hist.pop()
    cycle.append(i)
    if i == top:
        break

cycle.reverse()

cur = 1
while not cur == top and not K == 0:
    cur = A[cur]
    K -= 1

if cur == top:
    cur = cycle[K % len(cycle)]

print(cur)

Submission status: Runtime Error

Solution code:
n,k=map(int, input().split())
a=list(map(int, input().split()))
alist=[]
i=1
while a[i-1] not in alist:
  i=a[i-1]
  alist.append(i)
loop1=alist.index(a[i-1])
if k<loop1+1:
  print(alist[k-1])
else:
  lenloop=len(alist)-loop1
  print(alist[((k-loop1-1)%lenroop)+loop1])

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
next=0
visited=[0]*n #index:訪れたとき
teleport=[] #index
for i in range(k):
    now=next
    if visited[now]==0:
        visited[now]=i+1
        teleport.append(now)
        next=a[now]-1
        k-=1
    else:
        loop=i+1-visited[now]
        break
print(teleport[len(teleport)-loop+k%loop]+1)

Submission status: Runtime Error

Solution code:
import numpy as np 
import sys 

readline = sys.stdin.readline

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

# 愚直にやると計算量O(K)でTLEになる
# 同じ街にいったら操作打ち切りで配列を完結させる

# Teleport順の配列を作る
teleport = {1: True}
next_town = 1
for i in range(K):
    next_town = A[next_town - 1] # next_townがintで与えられる
    try: # 辞書を使用してO[1]で判定する
        teleport[next_town]
        dupulicate_town = next_town
        # 辞書をリストに変換
        teleport = list(teleport.keys())
        dupulicate_index = teleport.index(dupulicate_town)
        dupulicate_list = teleport[dupulicate_index:]
        break
    except KeyError:
        teleport[next_town] = True


if len(teleport) - 1 == K:
    print(teleport[-1])
else: # ループに入る場合
    consumption = len(teleport) - 1
    roop_num = K - consumption
    roop_index = roop_num % len(dupulicate_list)
    if roop_index == 0:
        print(dupulicate_list[-1])
    else:
        print(dupulicate_list[roop_index - 1])

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
A=list(map(int, input().split()))
now = 1
if n>=k:
    for i in k:
        now = A[now-1]
        exit()
past = [-1]*n
cnt = 0
while now not in past:
    past[cnt] = now
    now = A[now-1]
    cnt +=1
loop_size = cnt-past.index(now)
surplus = (k-past.index(now))%loop_size
for i in range(surplus):
    now = A[now-1]
print(now)