Problem:


Score: 400 points

Problem Statement

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

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

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

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

Constraints

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

1 \leq A_i \leq N

1 \leq K \leq 10^{18}

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

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

Sample Input 1

4 5
3 2 4 1

Sample Output 1

4

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

Sample Input 2

6 727202214173249351
6 5 2 5 3 2

Sample Output 2

2



Sample input:
4 5
3 2 4 1


Sample output:
4

Submission status: Wrong Answer

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


moves = [1]
i = 1

while True:
    next_i = A[i-1]
    if next_i in moves:
        break
    moves.append(next_i)
    i = next_i

p = moves.index(next_i)
l = len(moves) - p

ans = moves[p+(K-p)%l]

print(ans)

Submission status: Wrong Answer

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

  count=0
  now_point = 1
  root_list = [a_list[0]]
  while True:
    now_point = a_list[now_point - 1]
    count += 1
    if a_list[now_point - 1] in root_list:
      loop_list = root_list[root_list.index(a_list[now_point - 1]):]
      loop_num = len(loop_list)
      break
    else:
      root_list.append(a_list[now_point - 1])

  k = k % loop_num
  now_point = 1
  for i in range(k):
    now_point = a_list[now_point - 1]

  print(now_point)


if __name__ == '__main__':
  main()

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
ed=[]
d=set()
now=0
x=-1
while True:
    ed.append(now)
    d.add(now)
    ne=A[now]
    if ne in d:
        x=ne
        break
    else:
        now=ne
loop=[x]
now=x
while True:
    now=A[now]
    if now==x:
        break
    else:
        loop.append(now)
def ind(l,a):
    for i in range(len(l)):
        if a==l[i]:
            return i
dn=ind(ed,ne)
T=len(loop)
ans=loop[(K-dn)%T]
print(ans+1)

Submission status: Wrong Answer

Solution code:
def search(now, teleporter, limit):
    visit = [-1] * len(teleporter)
    cnt = 0
    
    while visit[now] == -1:
        if limit <= cnt:
            break
        
        visit[now] = cnt
        cnt += 1
        now = teleporter[now]
        
    
    return now, cnt, cnt - visit[now]
    

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

start, initial_cnt, repeat_num = search(0, a, 10**5 + 1)

#print(start, initial_cnt, repeat_num)

if k < initial_cnt:
    r = k
else:
    r = (k - initial_cnt) % repeat_num

#print(r)

ans, _, _ = search(start, a, r)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int, input().split()))
iti=1
count=0
sokuseki=[0]*n
while True:
    iti=a[iti-1]
    count+=1
    if sokuseki[iti-1]:
        m=((k-count)//(count-sokuseki[iti-1]))
        k=k-count-m*(count-sokuseki[iti-1])
        count=0
    sokuseki[iti-1]+=count
    if count==k:
        print(iti)
        exit()

Submission status: Wrong Answer

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

seen = dict()
goal = dict()

seen[1] = 0
goal[0] = 1

prev = targets[0]
startFlag = False
for i in range(1, k):
    seen[prev] = i
    goal[i] = prev
    current = targets[prev - 1]
    if current in seen:
        before = seen[current]

        finalGoal = k % (i + 1 - before)
        print(goal[finalGoal])
        exit()
    prev = current

print(goal[k-1])

Submission status: Wrong Answer

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

teleport = [-1] * (N+1)
teleport[0] = 1
for i in range(1, N+1):
    next_town = A[teleport[i-1]-1]
    teleport[i] = next_town
    if next_town == 1:
        break
mod = K % i
print(teleport[mod])

Submission status: Wrong Answer

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

a_dict = {}
for from_a, to_a in enumerate(a_list):
    a_dict[from_a+1] = to_a

now = 1
a_route = [now]
for _ in range(len(a_dict.keys())):
    now = a_dict[now]
    if now == 1:
        break
    a_route.append(now)

if k<=len(a_route)-1:
    print(a_route[k])
else:
    print(a_route[k%len(a_route)])

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split(" "))
tele=list(map(int,input().split(" ")))
c=[0]*n
times=0
city=1
for i in range(n):
    times+=1
    city=tele[city-1]
    if city in c:
        break
    c[times-1]=city

if k<=times:
    print(c[-(times-k)])
else:
    k-=times
    k=k%len(c)
    print(c[-(times-k)])

Submission status: Wrong Answer

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

visited_ls = [0] * (n+1)
tour_ls = []
now = 1
times = 1
while True:
    # 現在地についての処理
    tour_ls.append(now)
    visited_ls[now] += 1

    nex = a_ls[now]
    if visited_ls[nex]:
        first_ind = tour_ls.index(nex)
        before_loop = first_ind
        loop_ls = tour_ls[first_ind:times]
        break
    # 現在地を更新
    now = nex
    times += 1
ind = (k - before_loop) % len(loop_ls)
print(loop_ls[ind])

Submission status: Wrong Answer

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

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

def readInts():
  return list(map(int,input().split()))
def main():
    n,k = readInts()
    A = readInts()
    root = []
    ok = True
    l = 0
    dic = defaultdict(int)
    while True:
        if ok:
            a = 1
            ok = False
        else:
            a = root[-1]
        if not dic[A[a-1]]:
            dic[A[a-1]] = a
            root.append(A[a-1])
        elif dic[A[a-1]] != a:
            dic[A[a-1]] = a
            root.append(A[a-1])
        else:
            j = 0
            for i in range(len(root)):
                if A[a-1] == root[i]:
                    j = i
            root = root[j:]
            l = j
            #print(root)
            break

    #print(root)
    k = k - (l+1) if k - (l+1) >= 0 else k
    print(root[k%len(root)])
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
m = [-1]*n
t = 0
i = 0
while True:
  if m[t] != -1:
    r = i - m[t]
    break
  m[t] = i
  t = a[t]-1
  i += 1
b = k%r
for i in range(n):
  if m[i] == b:
    print(i+1)
    break

Submission status: Wrong Answer

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

havebeen=[1]
nidome=[]
current=1

for i in range(10**8):
  current=a[current-1]
  havebeen+=[current]
  if a[current-1] in nidome:
    break
  elif a[current-1] in havebeen:
    nidome+=[a[current-1]]
    if len(nidome)==1:
      tmp=i

if k<=tmp-1:
  print(havebeen[k-1])
else:
  print(nidome[(k-(tmp-1))%len(nidome)])

Submission status: Wrong Answer

Solution code:
n, k = map(int,input().split())
a = list(map(int, input().split()))
c = 1
s = 0
b = [0]*(n+1)
b[1] = 1
d = [0]*(n+1)
d[1] = 0

for i in range(n):
    c = a[c-1]
    b[c] += 1
    if b[c] == 2:
        s = i+1 - d[c]
        f = d[c]
        break
    d[c] = i+1

e = c
S = (k-f)%s
for i in range(S):
    e = a[e-1]
    #print(e)
#print(s)
#print(c)
print(e)

Submission status: Wrong Answer

Solution code:
n, k = [int(i) for i in input().split()]
a = [int(j) for j in input().split()]
dp = [0] * (n + 1)
for i in range(1, n + 1):
    dp[i] = a[dp[i - 1]] - 1
b = dp[n]
for j in range(n - 2, -1, -1):
    if dp[j] == b:
        period = n - j
        break
k = k % period
print(dp[k] + 1)

Submission status: Wrong Answer

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

x=1
l=[1]
for i in range(k):
    y=a[x-1]
    if y not in l:
        l.append(y)
        x=y
    else:
        x=y
        break

j=l.index(x)
mod=k%(len(l)-j)

print(l[mod])

Submission status: Wrong Answer

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

cnt = 0
x = 1
for i in range(N):
    y = A[x-1]
    cnt += 1
    if y == 1:
        break
    x = y

if N < K:
    s = K % cnt
else:
    s = K+1
x = 1
for i in range(s):
    y = A[x-1]
    x = y
print(y)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    A = LI_()

    visited = [False]*N

    city = A[0]
    teleport_cycle = [city]
    while not visited[A[city]]:
        city = A[city]
        teleport_cycle.append(city)
        visited[city] = True
    if A[0]==0:
        print(1)
    else:

        city_cycle_head = A[teleport_cycle[-1]]
        idx_cycle_head = teleport_cycle.index(city_cycle_head)
        length_cycle = len(teleport_cycle) - idx_cycle_head

        # print(teleport_cycle)

        if K-1<len(teleport_cycle):
            print(teleport_cycle[K-1]+1)
        else:
            K = idx_cycle_head + (K-idx_cycle_head)%length_cycle
            print(teleport_cycle[K-1]+1)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

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

here = 1
visited = [1]
for i in range(k):
    here = a[here]
    if(here in visited):
        tmp = visited.index(here)
        amari = (k - tmp)%(len(visited)-tmp)
        here = visited[tmp-1+amari]
        break
    else:
        visited.append(here)

print(here)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import sys
sys.setrecursionlimit(4100000)

n,m= map(int,readline().split())
a = list(map(int,readline().split()))

if a[0] == 1:
  print(1)
  exit()
  
cnt = n
for i,ai in enumerate(a):
  if i+1 == ai:
    cnt -= 1
    
k = m % cnt
d = []
def dfs(now,cc,d):
    if cc == k:
      return now
    else:
      next = a[now]
      next -= 1
      if not next in d:
        d.append(next)
        return dfs(next,cc+1,d)
      else:
        for i,di in enumerate(d[::-1]):
          if di == next:
            return (i+1,cc,now)

def f(now,cc):
    global mar
    if cc == mar:
      return now
    else:
      next = a[now]
      next -= 1
      return f(next,cc+1)
    
res = dfs(0,0,d)
if type(res) == int:
  print(res+1)
else:
  m -= res[1]
  mar = m % res[0]
  print(f(res[2],0)+1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[0]*n
r=[-1]*n
b=[]
lambda_1=lambda s:int(s)-1
a[:]=map(lambda_1, input().split())
#print(a)
c=0
for ii in range(len(a)):
	b.append(a[c])
	if r[a[c]]!=-1:
	    #print(b)
	    a0=b.index(r[a[c]])
	    k0=(k-(a0+1))%(len(b)-(a0+1))+a0
	    #print(a0)
	    #print(len(b)-(a0+1))
	    #print(a0,k0)
	    print(b[k0]+1)
	    exit()
	c=a[c]
	r[c]=c

print(a[len(a)-1])

Submission status: Wrong Answer

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

now = 1
k = k % n

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

print(now)

Submission status: Wrong Answer

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

    p_list = [1]
    ne_p = a[0]
    p_bool = [False for _ in range(n)]
    p_bool[0] = True
    check = False
    for _ in range(n):
        p_bool[ne_p-1] = True
        p_list.append(ne_p)
        ne_p = a[ne_p-1]
        # if ne_p in p_list:
        #     ind = p_list.index(ne_p)
        #     break
        if p_bool[ne_p-1]:
            check = True
            break
    #print(p_list)
    #print(p_bool)
    if check:
        ind = p_list.index(ne_p)
    else:
        ind = 0
    k = k - ind
    #print(ind)
    #print(k)
    #print(p_list)
    #print(k%(len(p_list)-ind))
    print(p_list[ind + k%(len(p_list)-ind)])

solve()

Submission status: Wrong Answer

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

tmp = a[0]

visit = []
visit.append(str(0))
visit.append(str(tmp-1))
visit_list = [0]*n

#print('start', 0)
count = 1
ans_on = 0
#print('tmp', tmp-1)
#print('############################')

if n >= k:
    loop_num = k
else:
    loop_num = n

for i in range(loop_num):
    #print('visited', visit)
    #print('count', count)
    count += 1
    tmp = a[tmp-1]
    #print('tmp', tmp - 1)

    if visit_list[tmp-1] == 1:
        on_index = visit.index(str(tmp-1))
        visit_len = len(visit)
        loop_list = visit[on_index:]

        k_ = k-count
        #if k_ % (visit_len-on_index) != 0:
        k_tmp =  k_ % (visit_len-on_index)
        #else:
        #    k_tmp = k_

        ans = loop_list[k_tmp]
        ans_on = 1
        #print('########################')
        #break

    visit.append(str(tmp-1))
    visit_list[tmp-1] = 1

    #print('########################')

if ans_on == 0:
    #print('last not loop', tmp+1)
    print(tmp+1)
else:
    #print('last', int(ans)+1)
    print(int(ans)+1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
n,k=map(int,input().split())

A=list(map(int,input().split()))
L=[None]*n
R=[0]*n
R=[1]
now=1
for i in range(n):
        now=A[now-1]
        if L[now-1] != None:
                index=R.index(now)
                break
        L[now-1]=now
        R.append(now)
        if i==n-1:
                index=n

if k<=index:
        print(R[k+1])
        exit()

r=(k-index)%(len(R)-index)
if index==n:
        print(R[1:][r])
        exit()
print(R[index:][r])

Submission status: Wrong Answer

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

route = [1]
ind = A[0]
ab=0

    
while len(route) <= N:
    if ind in route:
        b_ind = route.index(ind)
        break
    elif len(route)==K:
        print(route[:-1])
        ab=1
    route.append(ind)
    ind = A[ind-1]
if ab==0:
    
    a = (K-b_ind)%(len(route)-b_ind)
    print(route[a+b_ind])

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
index=[0]
index.append(A[0]-1)
flag=0
count=0
for _ in range(N):
    #print(index)
    t=index[-1]
    if (A[t]-1) in index:
        index.append(A[t]-1)
        flag=1
        break
    index.append(A[t]-1)
if flag==0:
    print(index[-1]+1)
    exit()
check = index[-1]
for i,c in enumerate(index):
    if c==check:
        a_path=i
        break
K-=a_path
t=len(index)-1-a_path
print(index[a_path+K%t]+1)
#print(index)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
now = 1
ss = set([0])
#ss = set([now-1])
for i in range(k):
    now = a[now-1]
    ss.add(now-1)
    if len(ss) != i+1:
        break
aa = k%(len(ss)+1)
for i in range(aa-1):
    now = a[now-1]
if k == 1:
	print(a[0])
else:
	print(now)

Submission status: Wrong Answer

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

def ml(a):
	cnt=1
	nxt=a[0]-1
	done.append(0)
	done.append(nxt)
	for i in range(len(a)):
		nxt = a[nxt]-1
		if nxt in done: 
			m = done.index(nxt) - 1
			l = cnt - m
			return (m+1,l)
		else: done.append(nxt)
		cnt+=1

# print(is_1(a))
m,l = ml(a)
num = (k-m)%l

# print(f"m={m},l={l}")
# print(f"done={done}")
# print(f"m+num={m+num}")
print(done[m+num]+1)

Submission status: Wrong Answer

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

MyList = [int(n) for n in MyList]

ANS = 0
visted = []

def Myfunc(A):
    return MyList[A] - 1

for i in range(K):
    if ANS in visted:
        beANS = K % len(visted)
        ANS = visted[beANS]
        print(ANS)
    ANS = Myfunc(ANS)
    visted.append(ANS)
    if i +1 == K:
        print(ANS+1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
L=list(map(int,input().split()))
L.insert(0,0)
#print(L)
visit=[0]*(n+1)
visit[L[0]]=1
prev=L[1]
count=0

for i in range(1,k):
	nex = L[prev]
	if visit[nex]==0:
		visit[nex]=1
	else:
		count+=i
		val=nex
		#print(i)
		#print(prev)
		break
	prev = nex
	
k-=count
k = k%(i-1)
#print(k)
for i in range(k):
	nex=L[prev]
	prev=nex
print(prev)

Submission status: Wrong Answer

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

went = [1, A[0]]

for i in range(1, K):
    next_town = A[went[i]-1]
    if next_town in went:
        head = went.index(next_town)
        loop = went[head:i + 1]
        last_town = (K - len(went) + 1) % len(loop)
        print(loop[last_town - 1])
        break
    else:
        went.append(next_town)

Submission status: Wrong Answer

Solution code:
nk = input('')
n = int(nk.split(' ')[0])
k = int(nk.split(' ')[1])

alist = input('').split(' ')
alist2 = []

next=1
loop_end=0
for i in range(len(alist)):
    next = int(alist[next-1])
    if next in alist2:
        loop_end=next
        break
    else:
        alist2.append(next)

head_size=alist2.index(loop_end)
loop_size=len(alist2) - head_size

k2=(k-head_size)%loop_size+head_size
pos=1
for i in range(k2):
    pos = int(alist[pos-1])

print(pos)

Submission status: Wrong Answer

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

visited = [1] + [0]*(n-1)
idx = [0] + [-1]*(n-1)
route = [0]
while True:
    now = a[route[-1]]
    if visited[now]:
        break
    visited[now] = 1
    idx[now] = len(route)
    route.append(now)

border = idx[a[route[-1]]]
non_loop = route[:border]
loop = route[border:]

print(loop[(k-len(non_loop))%len(loop)]+1)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
time = 0
roop = [1]
while(len(set(roop)) == len(roop)):
    roop.append(a[roop[-1]-1])
first = roop.index(roop[-1])
roop.pop(-1)
if(first != 0):
    atama = len(roop) - first
    gachiroop = roop[atama-1:]
    print(gachiroop[(k-atama+1)%len(gachiroop)])
else:
    print(roop[k%len(roop)])

Submission status: Wrong Answer

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


def main():
    N, K = map(int, input().split())
    A = list(map(lambda x: int(x) - 1, input().split()))

    visited = [False] * N
    route = []
    
    cnt = 0
    v = 0
    while visited[v] == False:
        visited[v] = True
        route.append(v)
        v = A[v]
        cnt += 1

    start = route.index(v)
    loop = cnt - start
    offset = (K - start) % loop
    res = route[start + offset] + 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split(" "))
tele=list(map(int,input().split(" ")))
c=[0]*n
times=0
city=1
for i in range(n):
    times+=1
    city=tele[city-1]
    if city in c:
        break
    c[times-1]=city

if k<times:
    print(c[-(times-k)])
elif k == times:
    print(city)
else:
    k-=times
    k=k%len(c)
    print(c[-(times-k)])

Submission status: Wrong Answer

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

l = []
used = [0 for _ in range(n)]

c = 0
flag = True
while 1:
    if not flag:
        l.append(c)
    if used[c] == 1 and l:
        break
    if not flag:
        used[c] = 1
    c = a[c]
    flag = False

p = 0
length = len(l)
for i in range(length):
    if l[i] == l[-1]:
        l = l[i:-1]
        p = i
        break

print(l[(k-p)%len(l)-1]+1)

Submission status: Wrong Answer

Solution code:
nk = input('')
n = int(nk.split(' ')[0])
k = int(nk.split(' ')[1])

alist = input('').split(' ')
alist2 = []

next=1
loop_end=0
for i in range(len(alist)):
    next = int(alist[next-1])
    if next in alist2:
        loop_end=next
        break
    else:
        alist2.append(next)

head_size=alist2.index(loop_end)
loop_size=len(alist2) - head_size
print(alist2)
print(len(alist2))
print(head_size)
print(loop_size)

k2=(k-head_size)%loop_size+head_size
print(k2)
pos=1
for i in range(k2):
    pos = int(alist[pos-1])

print(pos)