Problem:


Score : 1000 points

Problem Statement

For two permutations p and q of the integers from 1 through N, let f(p,q) be the permutation that satisfies the following:

The p_i-th element (1 \leq i \leq N) in f(p,q) is q_i.
Here, p_i and q_i respectively denote the i-th element in p and q.

You are given two permutations p and q of the integers from 1 through N.
We will now define a sequence {a_n} of permutations of the integers from 1 through N, as follows:

a_1=p, a_2=q

a_{n+2}=f(a_n,a_{n+1}) ( n \geq 1 )

Given a positive integer K, find a_K.

Constraints

1 \leq N \leq 10^5

1 \leq K \leq 10^9

p and q are permutations of the integers from 1 through N.

Input

Input is given from Standard Input in the following format:

N K
p_1 ... p_N
q_1 ... q_N

Output

Print N integers, with spaces in between.
The i-th integer (1 \leq i \leq N) should be the i-th element in a_K.

Sample Input 1

3 3
1 2 3
3 2 1

Sample Output 1

3 2 1

Since a_3=f(p,q), we just need to find f(p,q).
We have p_i=i here, so f(p,q)=q.

Sample Input 2

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

Sample Output 2

4 3 2 1 5

Sample Input 3

10 1000000000
7 10 6 5 4 2 9 1 3 8
4 1 9 2 3 7 8 10 6 5

Sample Output 3

7 9 4 8 2 5 1 6 10 3



Sample input:
3 3
1 2 3
3 2 1


Sample output:
3 2 1

Submission status: Wrong Answer

Solution code:
#get f
def make_f(p,q):
	N=len(p)
	f=[0 for i in range(N)]
	for i in range(N):
		f[p[i]-1]=q[i]
	return f



#input

N,K=input().split(" ")
N=int(N)
K=int(K)

p=input().split(" ")
p=[int(pi)for pi in p]

q=input().split(" ")
q=[int(qi)for qi in q]


A=[[],p,q]

for i in range(3,K+1):
	A.append(make_f(A[-2],A[-1]))

print(A[-1])

Submission status: Wrong Answer

Solution code:
import sys

l = raw_input().split()
N = int(l[0])
K = int(l[1])
P = [int(p) for p in raw_input().split()]
Q = [int(q) for q in raw_input().split()]

# print(N, K, P, Q)

def compose(P, Q):
    ret = [0]*len(P)
    for i in range(len(P)):
        ret[P[i] - 1] = Q[i]
    return ret

a = P
b = Q
order = 0

while True:
    # print(a, b)
    c = compose(a, b)
    a,b = b,c
    order += 1
    if a == P and b == Q:
 #       print(a, b)
        break

print(order)
#print(P, Q)
remains = K % order

for i in range(remains - 2):
    # print(i, a, b)
    c = compose(a, b)
    a,b = b,c

ans = ""
for i in range(len(b)):
    ans += str(b[i])
    if i < len(b):
        ans += " "

print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
p=[int(i)-1 for i in input().split()]
q=[int(i)-1 for i in input().split()]
def inv(seq):
    res=[0 for i in range(N)]
    for i in range(N):
        res[seq[i]]=i
    return seq
def times(seq1,seq2):
    res=[0 for i in range(N)]
    for i in range(N):
        res[i]=seq1[seq2[i]]
    return res
md=[[0 for i in range(N)] for i in range(6)]
for i in range(N):
    md[0][i]=p[i]
    md[1][i]=q[i]
for i in range(2,6):
    md[i]=times(md[i-1],inv(md[i-2]))
A=times(times(q,inv(p)),times(inv(q),p))
T=(K-1)//6
def expseq(seq,k):
    if k==0:
        return [i for i in range(N)]
    elif k==1:
        return seq
    elif k%2==0:
        return expseq(times(seq,seq),k//2)
    else:
        return times(expseq(times(seq,seq),k//2),seq)
tmp=expseq(A,T)
ans=times(times(tmp,md[(K-1)%6]),inv(tmp))
print(" ".join([str(i+1) for i in ans]))

Submission status: Wrong Answer

Solution code:
#D問題
N,K=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=[0 for i in range(N)]
for i in range(N):
    r[p[i]-1]=q[i]
if K%2==0:
    if K%4==0:
        for i in range(N):
            print(p[i],end=" ")
    else:
        for i in range(N):
            print(r[i],end=" ")
else:
    if K%4==1:
        for i in range(N):
            print(r[i],end=" ")
    else:
        for i in range(N):
            print(q[i],end=" ")

Submission status: Wrong Answer

Solution code:
#D
import numpy as np
n, k = map(int, input().split())
p = input().split()
q = input().split()

def permutate(seq, perm):
    perm_dic = {k:v for k, v in zip(perm, seq)}
    perm_items = sorted(perm_dic.items())
    return [v[1] for v in perm_items]

def fibonacci(k):
    # k >= 3
    if k == 1:
        return 1
    if k == 2:
        return 1
    a = 1
    b = 1
    for x in range(k-2):
        c = a + b
        a = b
        b = c
    return c

if k == 1:
    result = p
elif k == 2:
    result = q
else:
    p_count = fibonacci(k-2)
    q_count = fibonacci(k-1)
    p_count = p_count % n
    q_count = q_count % n
    temp = q
    for x in range (p_count):
        temp = permutate(temp, p)
    for x in range(q_count):
        temp = permutate(temp, q)
    result = temp
        

print(' '.join(result))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
ppp = list(map(int, input().split()))
qqq = list(map(int, input().split()))
ini_p = ppp[:]
ini_q = qqq[:]
i = 0
for i in range(k - 2):
    rrr = [q for p, q in sorted(zip(ppp, qqq))]
    if rrr == ini_p:
        break
    ppp = qqq
    qqq = rrr
else:
    print(*qqq)
    exit()

k = k % (i + 2)
ppp = ini_p
qqq = ini_q
for i in range(k - 2):
    rrr = [q for p, q in sorted(zip(ppp, qqq))]
    ppp = qqq
    qqq = rrr
print(*qqq)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, K = map(int, input().split())
p = np.array([int(_) for _ in input().split()])
q = np.array([int(_) for _ in input().split()])

def a(k, p, q, N):
  if k == 1:
    return p
  elif k == 2:
    return q
  for _ in range(k - 2):
    p, q = q, q[(p - 2) % N]
  return q
print(' '.join(map(str, a(K, p, q, N))))

Submission status: Wrong Answer

Solution code:
def f(p, q):
    list1 = [0 for k in range(len(p))]
    for i in range(len(p)):
        list1[p[i]-1] = q[i]
    return list1

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

p = list(map(int, input().split()))
q = list(map(int, input().split()))

a = p
b = q
for i in range(k-2):
    temp = b
    b = f(a,b)
    a = temp

print(b)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, k = (int(i) for i in input().split())
p = np.array([int(i) for i in input().split()])
q = np.array([int(i) for i in input().split()])

def f(p, q):
    return q[np.argsort(p)]

a_kk = q
a_k = f(p, q)
for i in range(4, k+1):
    a_kkk = a_kk
    a_kk = a_k
    a_k = f(a_kkk, a_kk)

print(' '.join(a_k.astype(str)))

Submission status: Wrong Answer

Solution code:
#D
n, k = map(int, input().split())
before = input().split()
after = input().split()
if k == 1:
    result = before
elif k == 2:
    result = after
else:
    for x in range(k - 2):
        sort_dict = {k: v for k, v in zip(before, after)}
        sorted_items = sorted(sort_dict.items())
        next_seq = [v[1] for v in sorted_items]
        before = after
        after = next_seq
    result = next_seq

print(' '.join(result))

Submission status: Wrong Answer

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

a=[p,q]

memo = {}

def perm(p,q):
    pq = ','.join(p) + ',' + ','.join(q)
    if pq in memo:
        return memo[pq]
    else:
        ans = [0] * len(p)
        for i in range(len(p)):
            ans[int(p[i])-1] = q[i]
        memo[pq] = ans
        return ans

if K>=3:
    for k in range(2,K):
        a.append(perm(a[k-2],a[k-1]))

print(a[-1])

Submission status: Time Limit Exceeded

Solution code:
def func(p, q):
    c = [0] * len(p)
    for i, pi in enumerate(p):
        c[pi - 1] = q[i]
    return(c)

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

#print("N={},K={},p={},q={}".format(N, K, p, q))

a = [[0]]
a.append(p)
a.append(q)
period = K + 1
for i in range(3, K + 1):
    a.append(func(a[i - 2], a[i - 1]))
#    print("a[{}] = {}".format(i, a[i]))
    if((p == a[i - 1]) & (q == a[i])):
        period = i - 2
        break

K = K % period
if(0 == K):
    K += period

#print("perid = {}, new K = {}".format(period, K))

print(" ".join(map(str, a[K])))

Submission status: Time Limit Exceeded

Solution code:
def func(p, q):
    c = [0] * len(p)
    for i, pi in enumerate(p):
        c[pi - 1] = q[i]
    return(c)

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

#print("N={},K={},p={},q={}".format(N, K, p, q))

a = [[0]]
a.append(p)
a.append(q)
period = K + 1
for i in range(3,K + 1):
    a.append(func(a[i - 2], a[i - 1]))
#    print("a[{}] = {}".format(i, a[i]))
    if((p == a[i - 1]) & (q == a[i])):
        period = i - 2
        break

K = K % period

#print("perid = {}, new K = {}".format(period, K))

print(" ".join(map(str, a[K])))

Submission status: Time Limit Exceeded

Solution code:
l = raw_input().split()
N = int(l[0])
K = int(l[1])
P = [int(p) for p in raw_input().split()]
Q = [int(q) for q in raw_input().split()]

# print(N, K, P, Q)

def compose(P, Q):
    ret = [0]*len(P)
    for i in range(len(P)):
        ret[P[i] - 1] = Q[i]
    return ret

a = P
b = Q
order = 0

while True:
    # print(a, b)
    c = compose(a, b)
    a,b = b,c
    order += 1
    if a == P and b == Q:
 #       print(a, b)
        break

# print(order)
#print(P, Q)
remains = K % order

for i in range(remains - 2):
    # print(i, a, b)
    c = compose(a, b)
    a,b = b,c

ans = ""
for i in range(len(b)):
    ans += str(b[i])
    if i < len(b):
        ans += " "

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**9)

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,k = na()
pp = na()
qq = na()

def f(p,q,h):
	if h and p == pp and q == qq:
		return [p,q]
	pq = [list(e) for e in zip(p, q)]
	pq.sort()
	return [p]+f(q,[i[1] for i in pq],True)

ppqq = f(pp,qq,False)
print(' '.join(map(str,ppqq[k%(len(ppqq)-2)-1])))

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
N,K=[int(i) for i in input().split(" ")]
p=[int(i) for i in input().split(" ")]
q=[int(i) for i in input().split(" ")]

p_origin=copy.copy(p)
q_origin=copy.copy(q)

def f(p,q):
    retval=[0 for i in range(N)]
    for _p,_q in zip(p,q):
        retval[_p-1]=_q
    return retval

if K==1:
    print(" ".join([str(i) for i in p]))
    sys.exit()
if K==2:
    print(" ".join([str(i) for i in q]))
    sys.exit()

loop=0

for i in range(K-2):
    tmp=f(p,q)
    p=q
    q=tmp
    if p==p_origin and q==q_origin:
        loop=i+1
        break

if loop==0:
    print(" ".join([str(i) for i in q]))

else:
    p=p_origin
    q=q_origin


    for i in range(K%loop-2+loop):
        tmp=f(p,q)
        p=q
        q=tmp
    print(" ".join([str(i) for i in q]))

Submission status: Accepted

Solution code:
def perpro(q,p):
    res=[-1]*len(p)
    for i in range(len(p)):
        res[i]=q[p[i]]
    return res

def inverse(p):
    res=[-1]*len(p)
    for i in range(len(p)):
        res[p[i]]=i
    return res

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

ide_ele=[i for i in range(N)]

for i in range(N):
    p[i]-=1
    q[i]-=1

invp=[-1]*N
for i in range(N):
    invp[p[i]]=i

invq=[-1]*N
for i in range(N):
    invq[q[i]]=i

A=perpro(q,perpro(invp,perpro(invq,p)))

kthA=[A]
for i in range(30):
    kthA.append(perpro(kthA[-1],kthA[-1]))

def _nthA(n):
    res=ide_ele
    for i in range(30):
        if n>>i&1==1:
            res=perpro(res,kthA[i])
    return res

def ntha(n):
    qqq=n//4
    r=n%4
    if r==0:
        return _nthA(qqq)
    elif r==1:
        return perpro(_nthA(qqq),q)
    elif r==2:
        return perpro(_nthA(qqq),perpro(q,invp))
    else:
        return perpro(_nthA(qqq),perpro(q,perpro(invp,invq)))

Q=(K-1)//3
r=(K-1)%3
ans=[]
if Q==0:
    if K==1:
        ans=p
    elif K==2:
        ans=q
    else:
        ans=perpro(q,invp)
else:
    if Q%2==0:
        if r==0:
            mid=p
            a=ntha(2*Q-1)
            ans=perpro(a,perpro(mid,inverse(a)))
        elif r==1:
            mid=q
            a=ntha(2*Q)
            ans=perpro(a,perpro(mid,inverse(a)))
        else:
            mid=perpro(q,invp)
            a=ntha(2*Q)
            ans=perpro(a,perpro(mid,inverse(a)))
    else:
        if r==0:
            mid=invp
            a=ntha(2*Q-1)
            ans=perpro(a,perpro(mid,inverse(a)))
        elif r==1:
            mid=invq
            a=ntha(2*Q)
            ans=perpro(a,perpro(mid,inverse(a)))
        else:
            mid=perpro(invq,p)
            a=ntha(2*Q)
            ans=perpro(a,perpro(mid,inverse(a)))

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

print(*ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

import numpy as np

# 可換なら6回周期。6個計算すると、交換子で共役とったものだとわかる。

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

P,Q = [np.array(input().split(), dtype=np.int32) for _ in range(2)]

P -= 1
Q -= 1

def inv(a):
    x = np.empty_like(a)
    x[a] = np.arange(len(x))
    return x

def mult_inv(a,b):
    # ab^{-1}
    c = np.empty_like(a)
    c[b] = a
    return c

def mult(a,b):
    return mult_inv(a,inv(b))

def power(a,n):
    if n == 0:
        return np.arange(len(a))
    x = power(a,n//2)
    x = mult(x,x)
    return mult(a,x) if n&1 else x

A = [P,Q]
for _ in range(4):
    A.append(mult_inv(A[-1],A[-2]))

q,r = divmod(K-1,6)
QP_Q_P = mult(mult_inv(mult_inv(Q,P),Q),P)
left = power(QP_Q_P,q)
right = inv(left)
answer = mult(mult(left, A[r]), right) + 1

print(' '.join(answer.astype(str)))

Submission status: Accepted

Solution code:
N,K=map(int,input().split());p=[int(i)-1for i in input().split()];q=[int(i)-1for i in input().split()];T=lambda s,t:[s[t[i]]for i in range(N)];m=[[0for i in[0]*N]for i in[0]*6];m[0]=p;m[1]=q
def I(s):
 r=[0]*N
 for i in range(N):r[s[i]]=i
 return r
for i in range(4):m[i+2]=T(m[i+1],I(m[i]))
E=lambda s,k:T(E(T(s,s),k//2),s)if k%2 else (E(T(s,s),k//2)if k else list(range(N)));t=E(T(T(T(q,I(p)),I(q)),p),~-K//6);print(*[str(i+1)for i in T(T(t,m[~-K%6]),I(t))])

Submission status: Accepted

Solution code:
N,K=map(int,input().split());p=[int(i)-1for i in input().split()];q=[int(i)-1for i in input().split()];T=lambda s,t:[s[t[i]]for i in range(N)];m=[[0for i in[0]*N]for i in[0]*6];m[0]=p;m[1]=q
def I(s):
 r=[0]*N
 for i in range(N):r[s[i]]=i
 return r
for i in range(4):m[i+2]=T(m[i+1],I(m[i]))
E=lambda s,k:T(E(T(s,s),k//2),s)if k%2 else (E(T(s,s),k//2)if k else list(range(N)));t=E(T(T(T(q,I(p)),I(q)),p),~-K//6);print(" ".join([str(i+1)for i in T(T(t,m[~-K%6]),I(t))]))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
p=[int(i)-1for i in input().split()]
q=[int(i)-1for i in input().split()]
T=lambda s,t:[s[t[i]]for i in range(N)]
m=[[0for i in[0]*N]for i in[0]*6];m[0]=p;m[1]=q
def I(s):
 r=[0]*N
 for i in range(N):r[s[i]]=i
 return r
for i in range(4):m[i+2]=T(m[i+1],I(m[i]))
E=lambda s,k:T(E(T(s,s),k//2),s)if k%2 else (E(T(s,s),k//2)if k else list(range(N)))
t=E(T(T(T(q,I(p)),I(q)),p),~-K//6);print(" ".join([str(i+1)for i in T(T(t,m[~-K%6]),I(t))]))

Submission status: Accepted

Solution code:
N,K=map(int,input().split());p=[int(i)-1 for i in input().split()];q=[int(i)-1 for i in input().split()];T=lambda s,t:[s[t[i]] for i in range(N)];m=[[0 for i in [0]*N] for i in [0]*6];m[0]=p;m[1]=q
def I(s):
 r=[0]*N
 for i in range(N):r[s[i]]=i
 return r
for i in range(4):m[i+2]=T(m[i+1],I(m[i]))
E=lambda s,k:(E(T(s,s),k//2) if k!=0 else list(range(N)))if k%2==0 else T(E(T(s,s),k//2),s);t=E(T(T(T(q,I(p)),I(q)),p),~-K//6);print(" ".join([str(i+1) for i in T(T(t,m[~-K%6]),I(t))]))

Submission status: Accepted

Solution code:
N,K=map(int,input().split());p=[int(i)-1 for i in input().split()];q=[int(i)-1 for i in input().split()]
def I(s):
 r=[0]*N
 for i in range(N):r[s[i]]=i
 return r
def T(s,t):return [s[t[i]] for i in range(N)]
m=[[0 for i in [0]*N] for i in [0]*6]
for i in range(N):m[0][i]=p[i];m[1][i]=q[i]
for i in range(4):m[i+2]=T(m[i+1],I(m[i]))
def E(s,k):
 if k%2==0:
  return E(T(s,s),k//2) if k!=0 else list(range(N))
 else:
  return T(E(T(s,s),k//2),s)
t=E(T(T(T(q,I(p)),I(q)),p),~-K//6);print(" ".join([str(i+1) for i in T(T(t,m[~-K%6]),I(t))]))

Submission status: Accepted

Solution code:
N,K=map(int,input().split());p=[int(i)-1 for i in input().split()];q=[int(i)-1 for i in input().split()]
def I(s):
 r=[0 for i in range(N)]
 for i in range(N):r[s[i]]=i
 return r
def T(s,t):
 r=[0 for i in range(N)]
 for i in range(N):r[i]=s[t[i]]
 return r
m=[[0 for i in range(N)] for i in range(6)];A=T(T(T(q,I(p)),I(q)),p);X=(K-1)//6
for i in range(N):m[0][i]=p[i];m[1][i]=q[i]
for i in range(2,6):m[i]=T(m[i-1],I(m[i-2]))
def E(s,k):
 if k==0:
  return [i for i in range(N)]
 elif k==1:
  return s
 elif k%2==0:
  return E(T(s,s),k//2)
 else:
  return T(E(T(s,s),k//2),s)
t=E(A,X);a=T(T(t,m[(K-1)%6]),I(t));print(" ".join([str(i+1) for i in a]))

Submission status: Accepted

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

p = list(map(int,input().split()))
q = list(map(int,input().split()))

def perprod(x,y): #xy
    nn = len(x)
    ret = [0 for i in range(nn)]

    for i in range(nn):
        ret[i] = x[y[i]-1]

    return ret

def perinv(x): #inverse
    nn = len(x)
    ret = [0 for i in range(nn)]
    for i in range(nn):
        ret[x[i]-1] =i+1

    return ret 

amari = (k-1) % 6
e = (k-1) //6

a =[[] for i in range(6)]

a[0] = p
a[1] = q
a[2] = perprod(a[1],perinv(a[0]))
a[3] = perprod(a[2],perinv(a[1]))
a[4] = perprod(a[3],perinv(a[2]))
a[5] = perprod(a[4],perinv(a[3]))

pp = perprod(perprod(a[1],perinv(a[0])),perprod(perinv(a[1]),a[0]))


ans1 = [i+1 for i in range(n)]

while e>0:
    if(e & 1): ans1 = perprod(ans1,pp)
    pp = perprod(pp,pp)
    e >>= 1

ans2 = perinv(ans1)

ans = perprod(ans1,a[amari])
ans = perprod(ans,ans2)

print(*ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
p=[int(i)-1 for i in input().split()]
q=[int(i)-1 for i in input().split()]
e=[i for i in range(N)]
def cir(x,y):
    z=[0]*N
    for i in range(N):
        z[i]=x[y[i]]
    return z
def inv(x):
    z=[0]*N
    for i in range(N):
        z[x[i]]=i
    return z
def f(x,y):
    return cir(y,inv(x))

def double(x,k):
    a=k
    t=x
    num=e
    while a!=0:
        if a%2==1:
            num=cir(num,t)
        a=a//2
        t=cir(t,t)
    return num
P=inv(p)
Q=inv(q)
#print(p,q,P,Q)
quo=(K-1)//6
r=K-quo*6-1
X=cir(q,cir(P,cir(Q,p)))
#Y=cir(P,cir(q,cir(p,Q)))
#Z=cir(q,double(Y,quo))
Z=double(X,quo)
A=cir(Z,cir(p,inv(Z)))
B=cir(Z,cir(q,inv(Z)))
#print(A,B,quo,r)
def g(n):
    if n==0:
        return A
    if n==1:
        return B
    return f(g(n-2),g(n-1))
L=g(r)
for i in range(N):
    L[i]+=1
print(' '.join(map(str,L)))

Submission status: Accepted

Solution code:
from operator import itemgetter


def get_identity():
    return list(range(1, n + 1))


def composition(ppp, qqq):
    return [ppp[q - 1] for q in qqq]


def reverse_composition(ppp, qqq):
    return [ppp[i] for i, q in sorted(enumerate(qqq), key=itemgetter(1))]


def solve(k, ppp, qqq):
    qp = reverse_composition(qqq, ppp)
    qpq = reverse_composition(qp, qqq)
    qpqp = composition(qpq, ppp)

    l, m = divmod(k - 1, 6)
    res = get_identity()
    tmp = qpqp
    while l:
        if l % 2 == 1:
            res = composition(res, tmp)
        tmp = composition(tmp, tmp)
        l >>= 1

    m = (k - 1) % 6
    if m == 0:
        base = ppp
    elif m == 1:
        base = qqq
    elif m == 2:
        base = reverse_composition(qqq, ppp)
    elif m == 3:
        res = composition(res, qqq)
        base = reverse_composition(get_identity(), ppp)
    elif m == 4:
        res = composition(res, qqq)
        res = reverse_composition(res, ppp)
        base = reverse_composition(get_identity(), qqq)
    elif m == 5:
        res = composition(res, qqq)
        res = reverse_composition(res, ppp)
        base = reverse_composition(get_identity(), qqq)
        base = composition(base, ppp)
    else:
        raise NotImplementedError

    ans = composition(res, base)
    ans = reverse_composition(ans, res)
    return ans


n, k = map(int, input().split())
ppp = list(map(int, input().split()))
qqq = list(map(int, input().split()))
print(*solve(k, ppp, qqq))

Submission status: Accepted

Solution code:
from operator import itemgetter


def get_identity():
    return list(range(1, n + 1))


def composition(ppp, qqq):
    return [ppp[q - 1] for q in qqq]


def reverse_composition(ppp, qqq):
    return [ppp[i] for i, q in sorted(enumerate(qqq), key=itemgetter(1))]


def solve(k, ppp, qqq):
    qp = reverse_composition(qqq, ppp)
    qpq = reverse_composition(qp, qqq)
    qpqp = composition(qpq, ppp)
   
    l, m = divmod(k - 1, 6)
    res = get_identity()
    tmp = qpqp
    while l:
        if l % 2 == 1:
            res = composition(res, tmp)
        tmp = composition(tmp, tmp)
        l >>= 1

    m = (k - 1) % 6
    if m == 0:
        base = ppp
    elif m == 1:
        base = qqq
    elif m == 2:
        base = reverse_composition(qqq, ppp)
    elif m == 3:
        res = composition(res, qqq)
        base = reverse_composition(get_identity(), ppp)
    elif m == 4:
        res = composition(res, qqq)
        res = reverse_composition(res, ppp)
        base = reverse_composition(get_identity(), qqq)
    elif m == 5:
        res = composition(res, qqq)
        res = reverse_composition(res, ppp)
        base = reverse_composition(get_identity(), qqq)
        base = composition(base, ppp)
    else:
        raise NotImplementedError

    ans = composition(res, base)
    ans = reverse_composition(ans, res)
    return ans


n, k = map(int, input().split())
ppp = list(map(int, input().split()))
qqq = list(map(int, input().split()))
print(*solve(k, ppp, qqq))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
p=[int(i)-1 for i in input().split()]
q=[int(i)-1 for i in input().split()]
def inv(seq):
    res=[0 for i in range(N)]
    for i in range(N):
        res[seq[i]]=i
    return res
def times(seq1,seq2):
    res=[0 for i in range(N)]
    for i in range(N):
        res[i]=seq1[seq2[i]]
    return res
md=[[0 for i in range(N)] for i in range(6)]
for i in range(N):
    md[0][i]=p[i]
    md[1][i]=q[i]
for i in range(2,6):
    md[i]=times(md[i-1],inv(md[i-2]))
A=times(times(q,inv(p)),times(inv(q),p))
T=(K-1)//6
def expseq(seq,k):
    if k==0:
        return [i for i in range(N)]
    elif k==1:
        return seq
    elif k%2==0:
        return expseq(times(seq,seq),k//2)
    else:
        return times(expseq(times(seq,seq),k//2),seq)
tmp=expseq(A,T)
ans=times(times(tmp,md[(K-1)%6]),inv(tmp))
print(" ".join([str(i+1) for i in ans]))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
p=[int(i)-1 for i in input().split()]
q=[int(i)-1 for i in input().split()]
def inv(seq):
    res=[0 for i in range(N)]
    for i in range(N):
        res[seq[i]]=i
    return res
def times(seq1,seq2):
    res=[0 for i in range(N)]
    for i in range(N):
        res[i]=seq1[seq2[i]]
    return res
md=[[0 for i in range(N)] for i in range(6)]
for i in range(N):
    md[0][i]=p[i]
    md[1][i]=q[i]
for i in range(2,6):
    md[i]=times(md[i-1],inv(md[i-2]))
A=times(times(times(q,inv(p)),inv(q)),p)
T=(K-1)//6
def expseq(seq,k):
    if k==0:
        return [i for i in range(N)]
    elif k==1:
        return seq
    elif k%2==0:
        return expseq(times(seq,seq),k//2)
    else:
        return times(expseq(times(seq,seq),k//2),seq)
tmp=expseq(A,T)
ans=times(times(tmp,md[(K-1)%6]),inv(tmp))
print(" ".join([str(i+1) for i in ans]))

Submission status: Accepted

Solution code:
from sys import stdin, stdout
from itertools import repeat
def pr(a):
    a = [x + 1 for x in a]
    stdout.write(' '.join(map(str, a)))
def main():
    n, k = map(int, stdin.readline().split())
    p = map(int, stdin.readline().split(), repeat(10, n))
    q = map(int, stdin.readline().split(), repeat(10, n))
    p = [x - 1 for x in p]
    q = [x - 1 for x in q]
    if k == 1:
        pr(p)
        return
    if k == 2:
        pr(q)
        return
    def inv(a):
        r = a[:]
        for i, x in enumerate(a):
            r[x] = i
        return r
    def comp(a, b):
        return [a[x] for x in b]
    pinv = inv(p)
    qinv = inv(q)
    b = q
    a = comp(q, pinv)
    if k == 3:
        pr(a)
        return
    w = [b, a]
    for i in xrange(4, 8):
        a, b = comp(a, inv(b)), a
        if k == i:
            pr(a)
            return
        w.append(a)
    y = range(n)
    x = comp(q, comp(pinv, comp(qinv, p)))
    r = (k - 8) / 6 + 1
    while r:
        if r & 1:
            y = comp(x, y)
        x = comp(x, x)
        r >>= 1
    t = comp(y, comp(w[(k - 8) % 6], inv(y)))
    pr(t)
main()

Submission status: Runtime Error

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

def f(p, q):
    a = [None for _ in range(len(p))]
    for idx, e_p in enumerate(p):
        a[e_p-1] = q[idx]
    return a

class A():
    def __init__(self, K, p, q):
        self.a = [None for _ in range(K)]
        self.a[0] = p
        self.a[1] = q

    def get_an(self, n):
        if self.a[n] is None:
            self.a[n] = f(self.get_an(n-2), self.get_an(n-1))
        return self.a[n]

a = A(K, p, q)
ans = a.get_an(K-1)
print(" ".join(map(str, ans)))

Submission status: Runtime Error

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

def prog(k):
    if(k==1):
        return p
    elif(k==2):
        return q
    else:
        r=[0]*n
        for i in range(1,n+1)
            r[prog(k-2)[i]]=prog(k-1)[i]
        return r

''.join(prog(k))

Submission status: Runtime Error

Solution code:
#D問題
N,K=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
p=[0]*N
for i in range(N):
    r[p[i]]=q[i]
if N%2==0:
    if N%4==0:
        for i in range(N):
            print(p[i],end="")
    else:
        for i in range(N):
            print(r[i],end="")
else:
    if N%4==1:
        for i in range(N):
            print(r[i],end="")
    else:
        for i in range(N):
            print(q[i],end="")

Submission status: Runtime Error

Solution code:
#D問題
N,K=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
p=[0]*N
for i in range(N):
    r[p[i]]=q[i]
if N%2==0:
    if N%4==0:
        for i in range(N):
          print(p[i],end="")
    else:
        for i in range(N):
          print(r[i],end="")
else:
    if N%4==1:
        for i in range(N):
          print(r[i],end="")
    else:
        for i in range(N):
          print(q[i],end="")

Submission status: Runtime Error

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

def prog(k):
    if(k==1):
        return p
    elif(k==2):
        return q
    else:
        r=[0]*n
        for i in range(3,n+1)
            r[prog(k-2)[i]]=prog(k-1)[i]
        return r

''.join(prog(k))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
ppp = list(map(int, input().split()))
qqq = list(map(int, input().split()))
ini_p = ppp.copy()
ini_q = qqq.copy()
i = 0
for i in range(k - 2):
    rrr = [q for p, q in sorted(zip(ppp, qqq))]
    if rrr == ini_p:
        break
    ppp = qqq
    qqq = rrr
else:
    print(*qqq)
    exit()

k = k % (i + 2)
ppp = ini_p
qqq = ini_q
for i in range(k - 2):
    rrr = [q for p, q in sorted(zip(ppp, qqq))]
    ppp = qqq
    qqq = rrr
print(*qqq)