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:
#!/usr/bin/env python3


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

    visited = [0] * (N+10)
    seq = []

    step = 0
    current = 1

    n1 = n2 = 0
    while(step<len(A)+1):
        #print(current)
        seq.append(current)
        step += 1
        visited[current] = step
        next_pos = A[current-1]
        if visited[next_pos]>0:
            n1 = visited[next_pos]
            n2 = step - n1 + 1
            #print(n1, n2)
            #print(n1-1, ((K-(n1-1))%n2))
            print(seq[n1-1+((K-(n1-1))%n2)])
            return
        else:
            visited[next_pos] = step
        current = next_pos

    print(seq[K])

    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

    visited = [0] * (N+10)
    seq = []

    step = 0
    current = 1

    n1 = n2 = 0
    while(step<len(A)+1):
        print(current)
        seq.append(current)
        step += 1
        visited[current] = step
        next_pos = A[current-1]
        if visited[next_pos]>0:
            n1 = visited[next_pos]
            n2 = step - n1 + 1
            print(n1, n2)
            print(n1-1, ((K-(n1-1))%n2))
            print(seq[n1-1+((K-(n1-1))%n2)])
            return
        else:
            visited[next_pos] = step
        current = next_pos

    print(seq[K])

    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

B = [1]
i = 0
count = 0

while True:
  if count == K:
    print(i)
    break
  elif A[i] in B:
    x = B.index(A[i])
    a = (K-x) % (len(B)-x)
    print(B[a+x])
    break
  else:
    B.append(A[i])
    i = A[i]-1
    count += 1

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
visited = [-1]*N
count = 0
v = 0
while visited[v] == -1:
    visited[v] = count
    v = A[v]-1
    count += 1
if visited[v] > K:
    print(A[K])
else:
    m = count - visited[v]
    K -= visited[v]
    K %= m
    print(A[K+visited[v]])

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
visited = [-1]*N
count = 0
v = 0
while visited[v] == -1:
    visited[v] = count
    v = A[v]-1
    count += 1
loop_length = count - visited[v]
K -= visited[v]
print(A[K%loop_length+visited[v]])

Submission status: Wrong Answer

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

now = 0
for d in range(N):
    if ((1 << d) & K) > 0:
        now = A[now]
    A = [A[a] for a in A]
print(now + 1)

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
from collections import deque

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	n, k = rli()
	A = list(rli())
	for i in range(n):
		A[i] -= 1
	L, seen = 0, set()
	cycle = deque()
	curr, cnt = 0, 0
	final = 0
	while cnt <= k:
		if cnt == k:
			print(curr + 1)
			return
		seen.add(curr)
		cycle.append(curr)
		L += 1
		curr = A[curr]
		if curr in seen:
			final = curr
			break
		cnt += 1
	while cycle and cycle[0] != final:
		cycle.popleft()
	L = len(cycle)
	last = k % L
	print(cycle[last] + 1)
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

#k=k%n
def teleport(n):
    return a[n-1]

place = a[0]
for _ in range(k):
    place = teleport(place)
print(place)

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
used = set()
num = [0]*n
used.add(0)
now = 0
cnt = 0
while True:
    cnt += 1
    if not a[now] in used:
        used.add(a[now])
        num[a[now]] = cnt
        now = a[now]
    else:
        lps = a[now]
        mod = cnt - num[a[now]]
        k %= mod
        break
now = 0
# print(mod, lps, k)
while k:
    now = a[now]
    k -= 1

print(now+1)

Submission status: Wrong Answer

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

k=k%n
def teleport(n):
    return a[n-1]

place = a[0]
for _ in range(k-1):
    teleport(place)
    place = teleport(place)
print(place)

Submission status: Wrong Answer

Solution code:
from collections import deque
n, k = map(int, input().split())
A = list(map(int, input().split()))
G = [[] for _ in range(n)]
for i in range(n):
    G[i].append(A[i] - 1)

seen = [0] * n
seen[0] = 1  # True, Falseだとスタート地点の0がループの起点だった場合に検知できない。
time_list = [-1] * n
time = 0

stack = deque([0])
while len(stack) > 0:
    now_v = stack.pop()
    if seen[now_v] > 1:
        x = time - time_list[now_v]
        break
    if time_list[now_v] < 0:
        time_list[now_v] = time
        time += 1
    next_v = G[now_v][0]
    seen[next_v] += 1
    stack.append(next_v)

tra_num = (k - time_list[now_v]) % x

tra_stack = deque([now_v])
cnt = 0

while cnt != tra_num:
    tra_now_v = tra_stack.pop()
    tra_next_v = G[tra_now_v][0]
    tra_stack.append(tra_next_v)
    cnt += 1

if cnt == 0:
    print(now_v + 1)
else:
    print(tra_next_v + 1)

Submission status: Wrong Answer

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

from collections import deque 
tmp = 1
num = []
seen = [-1]*(N+1)
 
while seen[tmp] == -1:
    seen[tmp] = tmp
    num.append(tmp)
    tmp = A[tmp]


l = num.index(tmp)
c = len(num) - l

if K < l:
    print(num[K-1])
else:
    print(num[(K-l)%c+l])

Submission status: Wrong Answer

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

from collections import deque 
tmp = 1
num = []
seen = [-1]*(N+1)
 
while seen[tmp] == -1:
    seen[tmp] = tmp
    num.append(tmp)
    tmp = A[tmp]


l = num.index(tmp)
c = len(num) - l

if K < len(num):
    print(num[K-1])
else:
    print(num[(K-l)%c+l])

Submission status: Wrong Answer

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

used_dict = {}
used_list = []

current_node = 0

while True:
    if current_node not in used_dict:
        used_dict[current_node] = True
        used_list.append(current_node)
        current_node = a_list[current_node]-1
    else:
        break

repeat_index = used_list.index(current_node)
repeat_list = used_list[repeat_index:]
repeat_length = len(used_list) - repeat_index

amari = (k-repeat_index) % repeat_length

# print(repeat_index,repeat_length,amari,used_list)
print(repeat_list[amari]+1)

Submission status: Wrong Answer

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

from collections import deque 
tmp = 1
num = []
seen = [-1]*(N+1)
 
while seen[tmp] == -1:
    seen[tmp] = tmp
    num.append(tmp)
    tmp = A[tmp]


l = num.index(tmp)

if K < len(num):
    print(num[K-1])
else:
    print(K%(len(num)-l) + l)

Submission status: Wrong Answer

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

b = []
ord = [-1 for x in range(n+1)]
c = 1
l = 1

v = 1
for x in range(k):
    if (ord[v] != -1):
        break
    ord[v] = x
    b.append(v)
    v = a[v-1]
c = len(b) - ord[v]
l = ord[v]

if (k < l):
    print(b[k])
else:
    k -= l
    k %= c
    print(b[l+k])

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from functools import reduce
from collections import deque
# from math import factorial
import collections
import math
import sys
sys.setrecursionlimit(2000000)

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

check = [0]*n
check[0] = 1
stack = [a[0]]
city = deque()
count = 0
while stack:
    x = stack.pop()
    count += 1
    if check[x-1] == 0:
        check[x-1] = 1
        city.append(x-1)
        stack.append(a[x-1])
    else:
        city.append(x-1)

idx = city.index(city[-1])
if idx == len(city)-1:
    idx = 0
    print(city[(k-idx) % len(city)-1]+1)
else:
    for i in range(idx+1):
        city.popleft()
    print((k-idx) % len(city)+1)

Submission status: Wrong Answer

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

import fractions
import copy
import bisect
import math
import numpy as np
import itertools
from itertools import combinations_with_replacement
#import math#数学的計算はこれでいける。普通に0.5乗しても計算可能
#w=input()
from operator import itemgetter
from sys import stdin
#input = sys.stdin.readline#こっちの方が入力が早いが使える時に使っていこう
from operator import mul
from functools import reduce
from collections import Counter
#from collections import deque

#input = stdin.readline


j=0
k=0
n=3
r=1
a=[0]
#n=int(input())
#r=int(input())
#print(M)
#A=int(input())
#B=int(input())
#print(N)
"1行1つの整数を入力を取得し、整数と取得する"


#number_list=list(map(int, input().split(" ")))#数字の時
#print(number_list)
"12 21 332 とか入力する時に使う"
"1行に複数の整数の入力を取得し、整数として扱う"

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
#メモ
for i in number_list:#こっちの方がrage使うより早いらしい
    print(number_list[i-1])#

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''

'''
x=[]
y=[]
for i in range(N):
    x1, y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)
print(x)
print(y)
"複数行に2数値を入力する形式 x座標とy座標を入力するイメージ"
'''

'''
mixlist=[]
for i in range(N):
    a,b=input().split()
    mixlist.append((int(a),b))
print(mixlist)
"複数行にintとstrを複合して入力するやつ，今回はリスト一つで処理している"
'''

'''
#array=[input().split()for i in range(N)]
#print(type(array[0][0]))
#print(array)
"正方行列にstr型の値を入力"
'''

#brray=[list(map(int, input().split(" ")))for i in range(N)]
#print(type(brray[0][0]))
#print(brray)
'''
入力
1 2
4 5
7 8
出力結果
[[1, 2], [4, 5], [7, 8]]
'''
"列数に関して自由度の高いint型の値を入力するタイプの行列"
#以下に別解を記載
#N, M = [int(i) for i in input().split()]
'''
table = [[int(i) for i in input().split()] for m in range(m)]

print(type(N))
print(N)
print(type(M))
print(M)

print(type(table))
print(table)
'''




#s=input()
#a=[int(i) for i in s]
#print(a[0])
#print([a])
#単数値．桁ごとに分割したい．入力と出力は以下の通り
#イメージとして1桁ごとにリストに値を入れているかんじ
#intを取ると文字列分解に使える
'''
入力
1234
出力
1
[[1, 2, 3, 4]]
'''




'''
word_list= input().split(" ")
print(word_list[0])
"連続文字列の入力"
"qw er ty とかの入力に使う"
"入力すると空白で区切ったところでlistの番号が与えられる"
'''



'''
A, B, C=stdin.readline().rstrip().split()#str style 何個でもいけることが多い
print(A)
"リストではなく独立したstr型を入れるなら以下のやり方でOK"
'''


#a= stdin.readline().rstrip()
#print(a.upper())
"aという変数に入っているものを大文字にして出力"


#a,b=map(int, input().split())  #int style 複数数値入力　「A B」みたいなスペース空いた入力のとき

#なんかうまく入力されるけど
#a=[[int(i) for i in 1.strip()]for 1 in sys.stdin]
#a = [[int(c) for c in l.strip()] for l in sys.stdin]]
#print(a)
#複数行の数値を入力して正方行列を作成


##############################################################################################
##############################################################################################
#under this line explains example calculation



'''
コンビネーションの組み合わせの中身を出力する形式
for i in itertools.combinations(brray, 2)
combinationsをpermutationsにすれば順列になる
今回なら(abc133B)
入力
1 2
5 5
-2 8
出力
[[1, 2], [5, 5], [-2, 8]]
もちろん一次元リストでも使えるし
何よりiもリストのように使えるので便利
'''

#nCr combination
'''
def cmb(n,r):
    #When n < r , this function isn't valid
    r= min(n-r,r)
    #print(n,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n-r, -1))
    #flochart mul(n,n-1)=x
    #next     mul(x,n-2)........(n-r+1,n-r)
    #mul read a,b and returns a*b

    under = reduce(mul, range(1, r+1))
    #print(over, under)
    #reduce is applied mul(1,2)=2
    #next   mul(2,3)=6
    #next   mul(6,4)=4.........last(r!,r+1)=r+1!

    return over // under
    #// is integer divide
    #calc example 5C2
    #over=5*4*3
    #under=3*2*1
a = cmb(n, r)
#print(a)
'''

'''
import itertools
from itertools import combinations_with_replacement

combinationについて
以下の違いを意識しよう
combinations() p, r 長さrのタプル列、ソートされた順で重複なし

combinations_with_replacement() p, r 長さrのタプル列、ソートされた順で重複あり


使用例 　　　　　　　　　　　                  出力　　
combinations('ABCD', 2)　　　　　　　　　　　　AB AC AD BC BD CD

combinations_with_replacement('ABCD', 2)　　 AA AB AC AD BB BC BD CC CD DD
'''



'''
#集計
#example
#a=[2,2,2,3,4,3,1,2,1,3,1,2,1,2,2,1,2,1]
#a=Counter(a)
for i in a.most_common(n):print(i)
#most_common()メソッドは、出現回数が多い要素順にCounterオブジェクトを並び替えます。
#引数にint型の数字nを設定した場合は、出現回数が高い上位ｎ個の要素を返します。
#何も設定しなければ、コンテナ型にあるすべての要素を出現回数の順番に並び替えたタプル型オブジェクトを返します。
#out put
#(2, 8)
 #(1, 6)
#(3, 3)
#(4, 1)
'''


#二部探索(binary search)
#A = [1, 2, 3, 3, 3, 4, 4, 6, 6, 6, 6]
#print(A)
#index = bisect.bisect_left(A, 5) # 7 最も左(前)の挿入箇所が返ってきている
#A.insert(index, 5)
#print(index)
#print(A)
'''
bisect.bisect_left(a, x, lo=0, h=len(a))
引数
a: ソート済みリスト
x: 挿入したい値
lo: 探索範囲の下限
hi: 探索範囲の上限
(lo, hiはスライスと同様の指定方法)
bisect_leftはソートされたリストaに対して順序を保ったままxを挿入できる箇所を探索します。leftが示す通り、aにすでにxが存在している場合は、挿入箇所は既存のxよりも左側になります。また、lo, hiを指定することで探索範囲を絞り込むことも可能です。デフォルトはaの全体が探索対象です。
'''

'''
素数の判定
'''


def is_prime(n):
    if n == 1: return False

    for k in range(2, int(np.sqrt(n)) + 1):
        #sqrt(n)+1以上は考えて約数はないので却下
        if n % k == 0:
            return False
            #割り切れたらFalse
    return True


'''
npのmaxとmaximumの違い
xs = np.array([1, -2, 3])
np.max(xs, 0)
この出力は3となります．[1, -2, 3]と0の4つの数字のうち，最も大きい値を出力します．

一方で，[max(1, 0), max(-2, 0), max(3, 0)]を出力したい時があります．
その時は，numpyのmaximum関数を用います．

xs = np.array([1, -2, 3])
np.maximum(xs, 0)  # [1, 0, 3]

'''

def factorial(x, mod=10**9+7):
    # x!
    # 階乗
    # ex) factorial(5) = 120
    tmp = 1
    for i in range(1, x+1):
        tmp = (tmp * i) % mod
    return tmp
    '''
    Basically, when you do a**d % n, you actually have to calculate a**d, which could be quite large.
    But there are ways of computing a**d % n without having to compute a**d itself, and that is what pow does.
    '''


########################################################################
########################################################################
#b2=a[:]  #1次元のときはコピーはこれで良い
#print(b2)

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b3=copy.deepcopy(a)  #2次元配列はこうコピーする
#print(b3)

def main():

    w=1
    j=0
    k=0
    #n=int(input())
    n,k=map(int, input().split(" "))
    a=list(map(int, input().split(" ")))#行先
    present=1#いまいる町の番号-1#リストの都合上そうなる
    city_num=[0]*(n+1)
    city_num[1]=1#ちゃんとint型を代入しろや
    a.insert(0, 0)
    #print(a)
    #print(city_num)
    for i in range(1,n+1):
        #print(a[present])
        present=a[present]
        if city_num[present]==0:
           city_num[present]=i
        else:
           #print("周期","余り")#ちゃんとでた
           #print(type(city_num[present]))#ものによってintになったりlistになったりする
           #city_num = [int(s) for s in city_num]
           #intはstrにしか使えナい
           quotient=i-city_num[present]+1#周期が出てくる
           remainder=city_num[present]-1#足が出ている部分が出てくる
           break
    #print(quotient,remainder)
    #print((k-remainder)%quotient)
    #print(a[remainder+(k-remainder)%quotient])
    #print(remainder+(k-remainder)%quotient)
    presnt=1
    #print(present)
    for i in range(1,(remainder+(k-remainder)%quotient)+1):

        present=a[present]
    print(present)
        #print(present)
    #print(present)
    #r=int(input())
    #dp= [[0]*3 for i in range(5)]#列　行
    #dp用の0の入ったやつ
    #dp= [[0]*(w+1) for i in range(n+1)]#0からwまでのw+1回計算するから
    #print(dp)＃初期条件が入る分計算回数+1列分必要(この場合は判断すべきものの数)
    DP = np.zeros(w+1, dtype=int)#これでも一次元リストが作れる
    exdp=np.zeros((3,4)) # ３×４の２次元配列を生成。2次元ならこう
    #dtypeは指定しないとfloatになる
    #for i in range(n):#ちょっとした入力に便利
    #    a, b = map(int, input().split())
        #dp[i][0] += [a]
        #これだとintとlistをつなぐことになって不適
    #    dp[i] += [a]
    #    dp[i] += [b]
        #これはうまくいく
        #やり方はいろいろあるということ
    #print(dp)


    "1行1つの整数を入力を取得し、整数と取得する"
    #nl=list(map(int, input().split(" ")))#数字の時
    #print(number_list)
    "12 21 332 とか入力する時に使う"
    "1行に複数の整数の入力を取得し、整数として扱う"
    #brray=[list(map(int, input().split(" ")))for i in range(N)
    #print(brray)


    #s=input()
    #a=[int(i) for i in s]#int取るとstrでも行ける
    #print(a)
    '''
    入力
    1234
    出力
    [1, 2, 3, 4]
    '''
    pin_l=["x" for i in range(10)]#内包表記に慣れろ
    #print(pin_l)

    ls = ["a", "b", "c", "d", "e"]


    #print(ls[2:5])
    #スライスでの取得

    #print(ls[:-3])
    #一番左端から右から3番目より左まで取得

    #print(ls[:4:2])
    #スライスで1個飛ばしで取得
    #ないときは左端スタート
    #始点のインデックス番号 : 終点のインデックス番号 : スキップする数+1
    #print(ls[::2])
    '''
    lsというリストの場合に、1つ飛びの値を取得したい場合には
    ls[::2]
    のようにします。こうすると、
    ["a", "c", "d"]と出力される
    '''

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# 4 5 (4 cities and 5 steps)
# 3 2 4 1

# 1 => 3
# 2 => 2
# 3 => 4
# 4 => 1

# 1 (0)
# 1 => 3 (1)
# 3 => 4 (2)
# 4 => 1 (3)

# 2 を作る 5 と2 と 1 を使う
# 2  = (5 - 3) % 2 + 3 - 1

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

paths = {}

for i in range(N):
    paths[i+1] = A_i[i]

# print('paths:', paths)

# 6 5 2 5 3 2

# 1 => 6 (1)
# 6 => 2 (2)
# 2 => 5 (3)
# 5 => 3 (4)
# 3 => 2 (5)

# loop_steps = 5 - 2 - 1 = 2
# 5 + 2 * m + r = 727202214173249351
# steps + loop_steps * m + r = K
# r = (K - steps) % loop_steps

state = 1
steps = 0
flag = False
known_states = {}

while steps < K:
    known_states[state] = steps # state => 2, steps => 2

    state = paths[state] # state => 5
    steps += 1 # steps => 3

    # print(f'steps: {steps}, state: {state}')

    if state in known_states and not flag: # state => 2 steps => 5
        loop_steps = steps - known_states[state]
        K = (steps - loop_steps) + (K - (steps - loop_steps))  % loop_steps
        print('loop_steps:', loop_steps)
        print('steps - loop_steps:', steps - loop_steps)
        print('K:', K)
        state = 1
        steps = 0
        # print('steps:', steps)
        flag = True
        # print('loop detected')



print(state)

Submission status: Wrong Answer

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

lists=[]
listt=[]
for i in range(10**20):
    s=A[s-1]
    listt=lists[:]
    lists.append(s)
    t+=1
    if len(set(lists))==len(set(listt)):
        break
    else:
        continue
k=0
for i in range(1,t):
    if lists[t-1]==lists[t-1-i]:
        k=i
if K<t-1-k:
  	print (lists[K])
else:
  	print (lists[(K-t+1)%k-1+(t-1-k)])

Submission status: Wrong Answer

Solution code:
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
# abc = [int(input()) for i in range(5)]
# n = int(input())
# n, m = list(map(int, input().split()))
check = [0]*n
check[0] = 1
stack = [a[0]]
city = []
count = 0
while stack:
    x = stack.pop()
    count += 1
    if check[x-1] == 0:
        check[x-1] = 1
        city.append(x-1)
        stack.append(a[x-1])
    else:
        city.append(x-1)

idx = city.index(city[-1])
if idx == len(city)-1:
    idx = 0
print(city[(k-idx) % len(city)-1]+1)

Submission status: Wrong Answer

Solution code:
# 4 5 (4 cities and 5 steps)
# 3 2 4 1

# 1 => 3
# 2 => 2
# 3 => 4
# 4 => 1

# 1 (0)
# 1 => 3 (1)
# 3 => 4 (2)
# 4 => 1 (3)

# 2 を作る 5 と2 と 1 を使う
# 2  = (5 - 3) % 2 + 3 - 1

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

paths = {}

for i in range(N):
    paths[i+1] = A_i[i]

# print('paths:', paths)

# 6 5 2 5 3 2

# 1 => 6 (1)
# 6 => 2 (2)
# 2 => 5 (3)
# 5 => 3 (4)
# 3 => 2 (5)

# loop_steps = 5 - 2 - 1 = 2
# 5 + 2 * m + r = 727202214173249351
# steps + loop_steps * m + r = K
# r = (K - steps) % loop_steps

state = 1
steps = 0
flag = False
known_states = {}

while steps < K:
    known_states[state] = steps # state => 2, steps => 2

    state = paths[state] # state => 5
    steps += 1 # steps => 3

    # print(f'steps: {steps}, state: {state}')

    if state in known_states and not flag: # state => 2 steps => 5
        loop_steps = steps - known_states[state]
        # print('loop_steps:', loop_steps)
        # print('steps - loop_steps', steps - loop_steps)
        K = (steps - loop_steps) + (K - (steps - loop_steps))  % loop_steps - 1
        # print('K:', K)
        steps = 0
        state = 1
        # print('steps:', steps)
        flag = True
        # print('loop detected')



print(state)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [*map(lambda x:int(x)-1, input().split())]

cnt = [0]*N
pre = 0
# for _ in range(N*2):
for _ in range(N*3):
    cnt[pre] += 1
    now = A[pre]
    pre = now


one = 0
loop = 0
for c in cnt:
    if c == 1: one += 1
    elif c > 1: loop += 1

k = max(0, K-one) % loop + one

# print('N,K',N,K)
# print('A',A)
# print('cnt',cnt)
# print('one',one,'loop', loop)
# print('K-one',K-one)
# print('min(0, K-one) \% loop',max(0, K-one) % loop)
# print('k',k)

pre = 0
for _ in range(k):
    now = A[pre]
    pre = now

ans = pre + 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
journey = [1]
dup = {}
for i in range(N+10000):
    journey.append(A[journey[-1] - 1])

end_idx, start_idx = 0, 0
dup = {}
for i, j in enumerate(journey):
    if j in dup:
        end_idx = i
        break
    else:
        dup[j] = 0
for i, j in enumerate(journey):
    if j == journey[end_idx]:
        start_idx = i
        break
b = end_idx - start_idx
m = (K - start_idx) % b
print(journey[start_idx + m])

Submission status: Wrong Answer

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

chk = [0]*(N+1)
town = 1
rt = []
roop = 0

while True:
    if chk[town] == 1:
        break
    rt.append(town)
    chk[town] = 1
    town = A[town-1]

if K <= rt.index(town):
    print(rt[K-1])
else:
    roop = (K-rt.index(town)) % (len(rt)-rt.index(town))
    print(rt[rt.index(town)+roop])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

    visited = [0] * (N+10)
    seq = []

    step = 0
    current = 1

    n1 = n2 = 0
    while(step<len(A)+1):
        #print(current)
        seq.append(current)
        step += 1
        visited[current] = step
        next_pos = A[current-1]
        if visited[next_pos]>0:
            n1 = visited[next_pos]
            n2 = step - n1 + 1
            print(seq[n1-1+((K-(n1-1))%n2)])
            return
        else:
            visited[next_pos] = step
        current = next_pos

    #print(n1, n2)
    #print(n1-1, ((K-(n1-1))%n2))
    print(current)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

N, K = [int(n) for n in input().split()]
A = [int(n) for n in input().split()]

dest = []

current = 0
next_dest = A[current]
seen = {}
count = 0

while not next_dest in seen:
    dest.append(next_dest)
    current = next_dest-1
    next_dest = A[current]
    seen[current+1] = count
    count += 1

repeat_index = seen[next_dest]
cycle_len = count - repeat_index

if K < len(dest):
    print(dest[K-1])
    sys.exit(0)
else:
    print(dest[repeat_index + ((K - repeat_index) % cycle_len) - 1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

    visited = [0] * (N+10)
    seq = []

    step = 0
    current = 1

    n1 = n2 = 0
    while(step<len(A)+1):
        #print(current)
        seq.append(current)
        step += 1
        visited[current] = step
        next_pos = A[current-1]
        if visited[next_pos]>0:
            n1 = visited[next_pos]
            n2 = step - n1 + 1
            print(seq[n1-1+((K-(n1-1))%n2)])
            return
        else:
            visited[next_pos] = step
        current = next_pos

    #print(n1, n2)
    #print(n1-1, ((K-(n1-1))%n2))
    print(seq[-1])
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [*map(lambda x:int(x)-1, input().split())]

cnt = [0]*N
pre = 0
for _ in range(N*2):
    cnt[pre] += 1
    now = A[pre]
    pre = now


one = 0
loop = 0
for c in cnt:
    if c == 1: one += 1
    elif c > 1: loop += 1


k = max(0, K-one) % loop + one

# print('N,K',N,K)
# print('A',A)
# print('cnt',cnt)
# print('one',one,'loop', loop)
# print('K-one',K-one)
# print('min(0, K-one) \% loop',max(0, K-one) % loop)
# print('k',k)

pre = 0
for _ in range(k):
    now = A[pre]
    pre = now

ans = pre + 1
print(ans)

Submission status: Wrong Answer

Solution code:
# 4 5 (4 cities and 5 steps)
# 3 2 4 1

# 1 => 3
# 2 => 2
# 3 => 4
# 4 => 1

# 1 (0)
# 1 => 3 (1)
# 3 => 4 (2)
# 4 => 1 (3)

# 2 を作る 5 と2 と 1 を使う
# 2  = (5 - 3) % 2 + 3 - 1

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

paths = {}

for i in range(N):
    paths[i+1] = A_i[i]

# print('paths:', paths)

# 6 5 2 5 3 2

# 1 => 6 (1)
# 6 => 2 (2)
# 2 => 5 (3)
# 5 => 3 (4)
# 3 => 2 (5)

# loop_steps = 5 - 2 - 1 = 2
# 5 + 2 * m + r = 727202214173249351
# steps + loop_steps * m + r = K
# r = (K - steps) % loop_steps

state = 1
steps = 0
flag = False
known_states = {}

while steps < K:
    known_states[state] = steps # state => 2, steps => 2

    state = paths[state] # state => 5
    steps += 1 # steps => 3

    # print(f'steps: {steps}, state: {state}')

    if state in known_states and not flag: # state => 2 steps => 5
        loop_steps = steps - known_states[state] - 1
        if not loop_steps:
            continue
        K = steps + (K - steps) % loop_steps - (known_states[state] + 1)
        steps = 0
        state = 1
        # print('steps:', steps)
        flag = True
        # print('loop detected')



print(state)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
list=[l[0]]
set=set()
num=0
while True:
  if l[list[num]-1] in set:
    break
  list.append(l[list[num]-1])
  set.add(l[list[num]-1])
  num+=1
y=list.index(l[list[num]-1])
x=len(list)-y
ans=list[y:]
print(ans[(k-y)%x-1])

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import math
from collections import deque 
from functools import reduce

# input = sys.stdin.readline

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

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

i_n = np.zeros(n)

idx = 1
for i in range(1, n+2):
    if (i_n[idx-1] != 0):
        rp = i_n[idx-1]
        break
    if i >= k:
        print(int(i_n[idx-1]))
        sys.exit(0)
    i_n[idx-1] = i
    idx = a[idx-1]
i_ncnt = np.where(i_n > 0, 1, 0)
cnt = sum(i_ncnt)
rp_cnt = (k - (rp - 1) ) % cnt
ai = rp
pl = rp
for _ in range(int(rp_cnt)+1):
    pl = a[int(ai)-1]
    ai = a[int(pl)-1]
print(int(pl))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
cnt = 0
visited = []
present = 1
loop = False
while not loop:
  if present in visited:
    loop = True
  else:
    cnt += 1
    visited.append(present)
    present = A[present-1]

ind = visited.index(present)
l = len(visited[ind:])
rest = (K-cnt) % l

present = visited[ind + rest]
    
print(present)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = [1]
c = 1
for i in range(n):
    ans.append(a[ans[i] - 1])
b = ans.index(ans[n])
if k < n - b:
    for l in range(k):
        c = a[c - 1]
else:
    for l in range((k-b)%(n-b)+b):
        c = a[c - 1]
print(c)

Submission status: Wrong Answer

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

T=[10**9]*(N+1)
label=[-1]*(N+1)
T[0]=1
label[1]=0
for i in range(1,N+1):
    T[i]=A[T[i-1]-1]
    if label[T[i]]>=0:
        poss=label[T[i]]
        pose=i
        break
    else:
        label[T[i]]=i

pos=K-poss-1
pos=pos%(pose-poss)
print(T[poss+pos+1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = [1]
c = 1
for i in range(n):
    ans.append(a[ans[i] - 1])
b = ans.index(ans[n])
if k < n - b:
    for l in range(k):
        c = a[c - 1]
    print(ans[k])
else:
    for l in range((k-b)%(n-b)+b):
        c = a[c - 1]
print(c)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
cnt = 0
visited = []
present = 1
loop = False
while not loop:
  if present in visited:
    loop = True
  else:
    cnt += 1
    visited.append(present)
    present = A[present-1]

ind = visited.index(present)
l = len(visited[ind:])
rest = (K-cnt) % l

while rest > 0:
    present = A[present-1]
    rest -= 1
    
print(present)

Submission status: Wrong Answer

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

T=[10**9]*(N+1)
label=[-1]*(N+1)
T[0]=1
label[1]=0
for i in range(1,N+1):
    T[i]=A[T[i-1]-1]
    if label[T[i]]>=0:
        poss=label[T[i]]
        pose=i
        break
    else:
        label[T[i]]=i

pos=K-poss+1-1
pos=pos%(pose-poss)
print(T[poss+pos])