Problem:


Score : 700 points

Problem Statement

We have a sequence of N \times K integers: X=(X_0,X_1,\cdots,X_{N \times K-1}).
Its elements are represented by another sequence of N integers: A=(A_0,A_1,\cdots,A_{N-1}). For each pair i, j (0 \leq i \leq K-1,\ 0 \leq j \leq N-1), X_{i \times N + j}=A_j holds.

Snuke has an integer sequence s, which is initially empty.
For each i=0,1,2,\cdots,N \times K-1, in this order, he will perform the following operation:

If s does not contain X_i: add X_i to the end of s.

If s does contain X_i: repeatedly delete the element at the end of s until s no longer contains X_i. Note that, in this case, we do not add X_i to the end of s.

Find the elements of s after Snuke finished the operations.

Constraints

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

1 \leq K \leq 10^{12}

1 \leq A_i \leq 2 \times 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_0 A_1 \cdots A_{N-1}

Output

Print the elements of s after Snuke finished the operations, in order from beginning to end, with spaces in between.

Sample Input 1

3 2
1 2 3

Sample Output 1

2 3

In this case, X=(1,2,3,1,2,3).
We will perform the operations as follows:

i=0: s does not contain 1, so we add 1 to the end of s, resulting in s=(1).

i=1: s does not contain 2, so we add 2 to the end of s, resulting in s=(1,2).

i=2: s does not contain 3, so we add 3 to the end of s, resulting in s=(1,2,3).

i=3: s does contain 1, so we repeatedly delete the element at the end of s as long as s contains 1, which causes the following changes to s: (1,2,3)→(1,2)→(1)→().

i=4: s does not contain 2, so we add 2 to the end of s, resulting in s=(2).

i=5: s does not contain 3, so we add 3 to the end of s, resulting in s=(2,3).

Sample Input 2

5 10
1 2 3 2 3

Sample Output 2

3

Sample Input 3

6 1000000000000
1 1 2 2 3 3

Sample Output 3

s may be empty in the end.

Sample Input 4

11 97
3 1 4 1 5 9 2 6 5 3 5

Sample Output 4

9 2 6



Sample input:
3 2
1 2 3


Sample output:
2 3

Submission status: Accepted

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

a = list(set(A))
a.sort()
R = {}
for i in range(len(a)):
  R[a[i]] = i

n = len(a)
L = [[] for _ in range(n)]
P = [[0, 0] for _ in range(N)]
for i in range(N):
  P[i][0] = R[A[i]]
  P[i][1] = len(L[R[A[i]]])
  L[R[A[i]]].append(i)

s = [R[A[0]], 0]
D = [0]

while True:
  while s[1] < len(L[s[0]]) - 1:
    t = L[s[0]][s[1] + 1]
    if t != N - 1:
      s = P[t + 1]
    else:
      break
  else:
    if L[s[0]][0] == N - 1:
      D.append(N)
      break
    s = P[L[s[0]][0] + 1]
    D.append(L[s[0]][s[1]])
    continue
  break

M = len(D)
m = (K - 1) % M

if m == M - 1:
  print()
  exit()
ans = []
s = P[D[m]]
t = L[s[0]][s[1]]

while t != N:
  if s[1] == len(L[s[0]]) - 1:
    ans.append(A[t])
    t += 1
  else:
    t = L[s[0]][s[1] + 1] + 1
  if t == N:
    break
  s = P[t]

print(" ".join(list(map(str, ans))))

Submission status: Accepted

Solution code:
def solve():
    N, K = [int(_) for _ in raw_input().split()]
    A = [(i, int(ele)) for i, ele in enumerate(raw_input().split())]
    sortA = sorted(A, key = lambda x: x[1])
    _next = [None] * N
    save = 0

    ## 1. Create _next list
    for i in range(1, N):
        if sortA[i][1] == sortA[save][1]:
            _next[sortA[i-1][0]] = sortA[i][0]
        else:
            _next[sortA[i-1][0]] = sortA[save][0]
            save = i
    _next[sortA[N-1][0]] = sortA[save][0]
    # print "_next: " + str(_next)

    ## 2. Create minimum times N0 to list X return empty list
    start = 0
    minCntToEmpty = 0
    while start != N:
        if _next[start] <= start:
            minCntToEmpty += 1
        start = _next[start] + 1
        # print "start: " +  str(start)
    minCntToEmpty +=1
    # print "minCntToEmpty: " + str(minCntToEmpty)

    ## 3. 4. CntDown = K%N0, run simulated start -> _next(start) + 1 until CntDown becomes 0
    cntDown = K % minCntToEmpty
    if cntDown == 0:
        print
        return
    # print "cntDown: " + str(cntDown)
    start = 0
    while cntDown > 1:
        if _next[start] <= start:
            cntDown -= 1
        start = _next[start] + 1
        # print "start: " +  str(start)

    ## 5. Run simulated to find final answer
    i = start
    # print "i: " + str(i)
    while i < N:
        if _next[i] <= i:
            print A[i][1],
            i += 1
        else:
            i = _next[i] + 1

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
hoge = [[]for i in range(200001)]
for i in range(N):
    hoge[A[i]].append(i)
NEXT = [-1]*N
for i in hoge:
    for j in range(-len(i),0):
        NEXT[i[j]] = i[j+1]
i = 1
p = 0
while i < K:
    #print(i,p)
    if NEXT[p] <= p:
        i += 1
    if NEXT[p] == N-1:
        i += 1
    p = (NEXT[p]+1)%N
    if p == 0:
        i = ((K-1)//(i-1))*(i-1)+1
while p < N:
    if NEXT[p] <= p:
        print(A[p],end = " ")
        p += 1
    else:
        p = NEXT[p]+1
print()

Submission status: Accepted

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

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

X = A * 2

Nextcount = [-1] * (2 * (10**5+1))
Nextind = [-1]*N

for i,x in enumerate(X):
    if 0 <= Nextcount[x] < N:
        Nextind[Nextcount[x]] = i

    Nextcount[x] = i

Repeatcount=0
NOW = 0

Repeatcount+=Nextind[NOW]-NOW+1
NOW=(Nextind[NOW]+1)%N

while NOW!=0:
    Repeatcount+=Nextind[NOW]-NOW+1
    NOW=(Nextind[NOW]+1)%N
    

Rep=(N*K)%Repeatcount
NOW=0

while True:
    if Nextind[NOW]-NOW+1<Rep:
        Rep-=Nextind[NOW]-NOW+1
        NOW=(Nextind[NOW]+1)%N

    else:
        break
    
#print(Rep,NOW)

from collections import Counter
C=Counter()
s=[]
for i in range(Rep):
    if X[(NOW+i)%N] in C:
        while X[(NOW+i)%N] in C:
            po=s.pop()
            C[po]-=1
            if C[po]==0:
                del C[po]

    else:
        s.append(X[(NOW+i)%N])
        C[X[(NOW+i)%N]]+=1

    #print(s,C)

print(*s)

Submission status: Accepted

Solution code:
# クソコードすぎる
N, K = map(int, input().split())
A = list(map(int, input().split()))
if N==1:
    if K%2==1:
        print(A[0])
    exit()
L = [-1] * (2*10**5+2)  # aを入れてindexを返す
Plus = [0]*N  # indexを入れて1か0
Next = [0]*N  # indexを入れてindex
for i, a in enumerate(A):
    l = L[a]
    if l==-1:
        L[a] = i
    else:
        Next[l] = i+1
        L[a] = i

if l!=-1:
    Next[l] = 0
    Plus[l] = 1
#print(Next)

for i, a in enumerate(A):
    l = L[a]  # あなたはどこから来たの
    if i <= l:
        Next[l] = i+1
        Plus[l] += 1
        L[a] = -1


#
# print(Next)
# print(Plus)

loop = Plus[0]
i = Next[0]
while i!=0:
    i_next = Next[i]
    if i_next==N:
        loop += 1
        i_next = 0
    #if i_next <= i:
    #    loop += 1
    loop += Plus[i]

    i = i_next
#
# print(loop)

TrueNext = Next.copy()
for i in range(N-1,-1,-1):
    p = Plus[i]
    if p==0:
        nn = TrueNext[i]
        if nn==N:
            nn = 0
        TrueNext[i] = TrueNext[nn]
#
# print(TrueNext)

k = K % loop
if k==0:
    exit()

start = 0
i=0
while i<k-1:
    if start==N:
        start=0
        i+=1
    if i==K-1:
        break
    start = TrueNext[start]
    i+=1
# print(start)

ans = []#[A[start]]
S = [0] * (2*10**5+2)
#S[ans[0]] = 1
for a in A[start:]:
    #print(a, ans)
    if S[a]==0:
        ans.append(a)
        S[a] = 1
    else:
        while S[a] != 0:
            a_ = ans.pop()
            S[a_] = 0
print(*ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,k = [int(i) for i in readline().split()]
a = [int(i) for i in readline().split()]

memo = dict()
res = [0]*(2*n)
for i,c in enumerate(a*2):
    if c in memo: res[memo[c]] = i+1
    memo[c] = i

#print(res)

res2 = res[:n]

for i in range(n-1,-1,-1):
    if res2[i] < n:
        res2[i] = res2[res2[i]]

cycle = [0]
offset = 0
now = res2[0]-n

while now != 0:
    if now == n:
        offset = 1
        break
    else:
        cycle.append(now)
        now = res2[now]-n

#print(res2)
#print(cycle,offset)

l = len(cycle)
k-=1
k %= (l+offset)

#print("k =",k)

if k != l: ans = cycle[k]
else: exit()
while res[ans] < n:
    ans = res[ans]

"""
if k != l: ans = p = cycle[k]
else: ans = p = n+1
while p <= n:
    ans = p
    p = res[p]
#    print(ans,p)
"""


if ans >= n: exit()
else:
    s = []
    ss = set()
    for i in range(ans,n):
        if a[i] in ss:
            while a[i] in ss:
                c = s.pop()
                ss.remove(c)
        else:
            s.append(a[i])
            ss.add(a[i])
    
print(" ".join(map(str,s)))

Submission status: Accepted

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

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    D = {}
    for j,a in enumerate(A):
        D[a] = D.get(a,[])+[j]

    t,k = 0,0
    T = [0]
    while True:
        k = (D[A[t]].index(t)+1)%len(D[A[t]])
        if k == 0:
            T.append(A[t])
        t = (D[A[t]][k]+1)%N
        if t == 0:
            break

    if T == [0]:
        return ''
    if K == 1 or (K-1)%len(T) == 0:
        t = 0
    else:
        t = D[T[(K-1)%len(T)]][0]+1
    S = []
    flag = False
    while t < N:
        k = (D[A[t]].index(t)+1)%len(D[A[t]])
        if k == 0:
            S.append(A[t])
            t += 1
        else:
            t = D[A[t]][k]+1

    res = ' '.join(map(str,S))

    return str(res)

if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

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

def main():
    n, k = rli()
    la = rli()
    MOD = len(la)
    lb = [-1 for _ in range(len(la))]
    periods = dict()
    for i, a in enumerate(la):
        periods.setdefault(a, [])
        periods[a].append(i)
    for v in periods.values():
        for i, e in enumerate(v):
            if i == len(v)-1:
                lb[e] = (v[0] + 1) % MOD
            else:
                lb[e] = (v[i+1] + 1) % MOD
    loop = [0]
    b = 0
    while True:
        nb = lb[b]
        if nb == 0:
            break
        if nb-b <= 1:
            loop.append(nb)
        b = nb
    # 周期を計算
    period = len(loop)
    if loop[-1] == len(loop)-1:
        loop.append(None)
        period += 1

    start = loop[(k-1)%period]
    if start is None:
        print()
        return
    lc = la[start:]

    counts = dict()
    for i, a in enumerate(lc):
        counts.setdefault(a, 0)
        counts[a] += 1

    ans = []
    target = None
    for a in lc:
        if target is None:
            count = counts[a]
            if counts[a] >= 2:
                target = a
            else:
                ans.append(a)
        else:
            counts[a] -= 1
            if a == target:
                counts[a] -= 1
                target = None
    # print(la[start:], lc)
    # print(lb, loop)
    print(" ".join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A += A
d = {}
da = {}
for i in range(2*N):
    a = A[i]
    if a in da:
        d[da[a]] = i
    da[a] = i
        
for i in range(N):
    if d[i] >= N:
        d[i] %= N


s = 0
k = K
while k > 1:
    if d[s]<=s:
        k -= 1
    if d[s] == N-1:
        k = K%(K-k+1)
    s = (d[s]+1)%N

if k == 0:
    print('')
else:
    ans = []
    while s <= N-1:
        if s < d[s]:
            s = d[s]+1
        else:
            ans.append(str(A[s]))
            s += 1
    print(' '.join(ans))

Submission status: Accepted

Solution code:
# import sys
# input = sys.stdin.readline
inf = 10 ** 18
P = 10 ** 9 + 7

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

d_x = {}
for idx, Ai in enumerate(A):
    if str(Ai) not in d_x.keys():
        d_x[str(Ai)] = [idx]
    else:
        d_x[str(Ai)].append(idx)

tab_jump = [None] * N
for key in d_x.keys():
    for i in range(len(d_x[key]) - 1):
        tab_jump[d_x[key][i]] = d_x[key][i + 1]
    tab_jump[d_x[key][-1]] = d_x[key][0]

ans = []
pos = 0
while True:
    # print("#", pos)
    if pos >= N * K: break
    pos_src = pos % N
    pos_dst = tab_jump[pos_src]
    if pos_src < pos_dst:
        pos_nxt = pos + (pos_dst - pos_src) + 1
    else:
        pos_nxt = pos + (pos_dst - pos_src) + N + 1
    #
    if pos_nxt > N * K:
        ans.append(A[pos_src])
        pos += 1
    else:
        if pos_nxt % N == 0:
            K_iter = pos_nxt // N
            pos = N * ((K // K_iter) * K_iter)
        else:
            pos = pos_nxt

if len(ans) > 0:
    print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
A = list(map(int,input().split()))
MAX = 2 * 10**5+1
nxt = [-1 for i in range(MAX)]

last_index = [-1 for i in range(MAX)]
next_index = [-1 for i in range(MAX)]
first_index = [-1 for i in range(MAX)]
for i in range(N):
	a = A[i]
	last = last_index[a]
	if last >= 0:
		next_index[last] = i
	else:
		first_index[a] = i
	last_index[a] = i

start_stat = 0
while True:
	current = first_index[start_stat] + 1
	while current < N and next_index[current] != -1:
		current = next_index[current] + 1
	if current >= N:
		nxt[start_stat] = 0
		break
	else:
		stat = A[current]
		nxt[start_stat] = A[current]
		if nxt[A[current]] == -1:
			start_stat = A[current]
			continue
		else:
			break

order = [0]
in_order = [False for i in range(MAX)]
in_order[0] = True
last_stat = nxt[0]
while not in_order[last_stat]:
	order.append(last_stat)
	in_order[last_stat] = True
	last_stat = nxt[last_stat]
a,b = 0,len(order)
for x in order:
	if x == last_stat:
		break
	else:
		a += 1
		b -= 1
stat_index = K if K < a else (K-a) % b
init_status = order[stat_index]
before_stat = order[(stat_index - 1) % len(order)]
current = first_index[before_stat] + 1
if init_status == 0:
	print("")
	exit()
ans = []
while current < N:
	if next_index[current] != -1:
		current = next_index[current] + 1
	else:
		ans.append(A[current])
		current += 1
print( " ".join(list(map(str, ans))))

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
AA=[0]*n
B=[2*n+1]*(2*(10**5)+1)
for i in reversed(range(n)):
  B[A[i]]=n+i+1
for i in reversed(range(n)):
  AA[i]=B[A[i]]-(i+1)
  B[A[i]]=i+1
count,index,inc=0,0,0
Chk=[0]*n
flag=False
while count<n*k:

  inc=AA[index]+1
  count+=inc  
  index=(index+inc)%n
  if Chk[index]!=0 or index==0:
    if flag==False:
      dd=count-Chk[index]
      count+=(((n*k)-count)//dd)*dd
      flag=True
  Chk[index]=count

count-=inc
index=(index+n-inc)%n

d=n*k-count
Ans1=A+A
Ans2=AA+AA
Ans=[]
i=index
while i<d+index:
  if i+Ans2[i]>=d+index:
    Ans.append(Ans1[i])
    i+=1
  else:
    i+=Ans2[i]+1
print(*Ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a_list=list(map(int,input().split()))
dp=[-1]*(n+1)
dp[n]=0
D={}
for i in range(n-1,-1,-1):
    if not a_list[i] in D:
        dp[i]=a_list[i]
        D[a_list[i]]=i+1
    else:
        dp[i]=dp[D[a_list[i]]]
        D[a_list[i]]=i+1
first={}
for i in range(n):
    if not a_list[i] in first:
        first[a_list[i]]=i
cycle=[dp[0]]
i=dp[0]
while True:
    if i==0:
        break
    ne=first[i]
    i=dp[ne+1]
    cycle.append(i)
cycle.pop()
cycle=[0]+cycle
T=len(cycle)
order=k%T
if 1<=order:
    start=cycle[order-1]
    check={}
    if start==0:
        ans=[]
        for i in range(n):
            if ans==[]:
                ans.append(a_list[i])
                check[a_list[i]]=0
            else:
                if a_list[i] in check:
                    ans=ans[:check[a_list[i]]]
                    temp={}
                    for j in check:
                        if check[j]<check[a_list[i]]:
                            temp[j]=check[j]
                    check=temp
                else:
                    ans.append(a_list[i])
                    check[a_list[i]]=len(ans)-1
    else:
        ans=[]
        x=first[start]
        for i in range(x+1,n):
            if ans==[]:
                ans.append(a_list[i])
                check[a_list[i]]=0
            else:
                if a_list[i] in check:
                    ans=ans[:check[a_list[i]]]
                    temp={}
                    for j in check:
                        if check[j]<check[a_list[i]]:
                            temp[j]=check[j]
                    check=temp
                else:
                    ans.append(a_list[i])
                    check[a_list[i]]=len(ans)-1
    for i in ans:
        print(i,end='')
        print(' ',end='')
else:
    print()

Submission status: Accepted

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

M = [None]*(max(A)+1)
T = [None]*N
for i,a in enumerate(A):
    M[a] = i

for i,a in enumerate(A):
    T[M[a]]=(i+1)%N
    M[a]=i

ptr=0
ptr_head = [ptr]
while True:
    ptr_next = T[ptr]
    if ptr_next==0: break
    if ptr_next <= ptr+1: ptr_head.append(ptr_next)
    ptr = ptr_next

period = len(ptr_head)
if T[-1]==0: period+=1

if K % period==0:
    print()
    exit()

ret = []
ptr = ptr_head[K % period - 1]
while ptr<N:
    ptr_next = T[ptr]
    if ptr_next > ptr+1:
        ptr = ptr_next
    elif ptr_next==0 and ptr!=N-1:
        break
    else:
        ret.append(A[ptr])
        ptr+=1

print(' '.join(map(str, ret)))

Submission status: Accepted

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

memo = {}
nxts = [None] * N
for i, x in enumerate(A + A):
  if x in memo:
    nxts[memo[x] % N] = i % N
  memo[x] = i

k = 0
visited = [-1] * N
p = 0
flag = False
ans = []
while k < K:
  if flag == False and visited[p] >= 0:
    vp = visited[p]
    k = vp + ((K-1) - vp) // (k - vp) * (k - vp)
    flag = True
  visited[p] = k
  nxt = nxts[p]
  if k == K-1 and nxt <= p:
    ans.append(A[p])
    nxt = p + 1
    if nxt >= N:
      break
  else:
    if nxt <= p:
      k += 1
    nxt = nxt + 1
    if nxt >= N:
      nxt %= N
      k += 1
  p = nxt

print(' ' .join(map(str, ans)))

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
hoge = [[]for i in range(200001)]
for i in range(N):
    hoge[A[i]].append(i)
NEXT = [-1]*N
for i in hoge:
    for j in range(-len(i),0):
        NEXT[i[j]] = i[j+1]
i = 1
p = 0
while i < K:
    #print(i,p)
    if NEXT[p] <= p:
        i += 1
    if NEXT[p] == N-1:
        i += 1
    p = (NEXT[p]+1)%N
    if p == 0:
        i = (K//(i-1))*(i-1)+1
while p < N:
    if NEXT[p] <= p:
        print(A[p],end = " ")
        p += 1
    else:
        p = NEXT[p]+1
print()

Submission status: Accepted

Solution code:
import bisect

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

d = {}
for i, a in enumerate(A):
    if a in d:
        d[a].append(i)
    else:
        d[a] = [i]

loop_cnt = 0
sp = []
p = 0
fp = 1
top = A[0]
while True:
    loop_cnt += 1
    while fp < N:
        np = bisect.bisect_left(d[top], fp)
        if np < len(d[top]):
            p = d[top][np] + 1
            fp = p+1
            if p < N:
                top = A[p]
        else:
            break
    if p >= N:
        break
    top = A[p]
    sp.append(p)
    fp = 0

k = K % loop_cnt - 1
if k == -1:
    exit()
p = sp[k]
s = []
while p < N:
    top = A[p]
    while True:
        np = bisect.bisect_left(d[top], p+1)
        if np < len(d[top]):
            p = d[top][np] + 1
            if p < N:
                top = A[p]
        else:
            break
    if p < N:
        s.append(top)
        p += 1

print(' '.join(map(str, s)))

Submission status: Accepted

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

if n == 1:
    print(*(aaa * (k % 2)))
    exit()

follow = [-1] * n
tmp = {}
fix = 0
while True:
    for i in range(n):
        a = aaa[i]
        if a in tmp:
            follow[tmp[a]] = (i + 1) % n
            tmp[a] = i
            fix += 1
        else:
            tmp[a] = i
    if fix >= n:
        break
# print(follow)
loop = 1
i = 0
while True:
    j = follow[i]
    if j == 0:
        if i == n - 1:
            loop += 1
        break
    if i + 1 >= j:
        loop += 1
    # print(i, j, loop)
    i = j

k %= loop
if k == 0:
    print()
    exit()

# print(k, loop)


def simulate(aaa, s, follow):
    tmp = []
    exs = set()
    for a in aaa[s:]:
        if a in exs:
            while True:
                b = tmp.pop()
                exs.remove(b)
                if a == b:
                    break
        else:
            tmp.append(a)
            exs.add(a)

    # i = s
    # while i != 0:
    #     j = follow[i]
    #     if j == 0:
    #         if i == n - 1:
    #             tmp.append(aaa[i])
    #         break
    #     elif i + 1 >= j:
    #         tmp.append(aaa[i])
    #         i = (i + 1) % n
    #     else:
    #         i = j
    return tmp


# print(simulate(aaa * 5, 0, follow))
# print(simulate(aaa * 6, 0, follow))

i = 0
loop = 1
while loop <= k:
    j = follow[i]
    if i + 1 >= j:
        if loop == k:
            print(*simulate(aaa, i, follow))
            break
        loop += 1
    i = j

Submission status: Accepted

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

if N==1:
  if K%2:
    print(A[0])
  else:
    print('')
  exit()
  

#print(*range(10000))

def func(L):
  s = []
  for l in L:
    if l in s:
      del s[s.index(l):]
      #s_set.remove(l)
    else:
      s.append(l)
      #s_set.add(l)
  return s




index_dict={}
for i,a in enumerate(A):
  index_dict.setdefault(a,[]).append(i)

next_i = [0]*N
cycle_i = [0]*N
for k,v in index_dict.items():
  for i in range(len(v)):
    next_i[v[i]] = (v[(i+1)%len(v)]+1)%N
    cycle_i[v[i]] = (i+1)//len(v)
#print(next_i)
#print(cycle_i)

from_in_cycle=[]

i = 0
while True:
  j = next_i[i]
  if cycle_i[i]:
    from_in_cycle.append(i)
  i = j
  # 循環の評価
  if i==0:
    break
    
#print(from_in_cycle)

if from_in_cycle:
  k = K%(len(from_in_cycle)+1)
  #print(*func(A[from_in_cycle[k-1]:]))

  ans = []
  i = from_in_cycle[k-1]
  while i < N:
    if cycle_i[i]:
      ans.append(A[i])
      i += 1
    else:
      if next_i[i]==0:
        break
      i = next_i[i]
  print(*ans)


else:
  print('')

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect

def solve(K,A):
    N = len(A)
    indices = defaultdict(list)
    for i,a in enumerate(A):
        indices[a].append(i)

    memo = [False]*N
    memo[0] = True
    trace = [0]
    cnt = [0]
    while True:
        i = trace[-1]
        c = cnt[-1]
        l = indices[A[i]]
        j = (l[bisect(l,i)%len(l)]+1)%N
        if j == 0 and i+1==N:
            c += 2
        elif j <= i+1:
            c += 1
        trace.append(j)
        cnt.append(c)
        if memo[j]:
            break
        else:
            memo[j] = True

    i = trace.index(trace[-1])

    period = cnt[-1] - cnt[i]
    if K > cnt[i]:
        K = (K-cnt[i])%period + cnt[i]
    if K == 0:
        return tuple()
    head = trace[bisect(cnt, K-1)-1]
    # print(cnt)
    # print(trace)
    # print(period)
    # print(K)
    # print(head)
    ans = []
    cur = head
    while cur < N:
        l = indices[A[cur]]
        j = bisect(l, cur)
        if j == len(l):
            ans.append(cur)
            cur += 1
        else:
            cur = l[j]+1
    return tuple(A[i] for i in ans)

def naive(K,A):
    s = {}
    l = []
    for k in range(K):
        for a in A:
            try:
                i = l.index(a)
                l = l[:i]
            except ValueError:
                l.append(a)
    return tuple(l)

# from random import randrange

# for n in range(100):
#     K = randrange(1,4)
#     A = [randrange(10) for _ in range(10)]
#     s1 = solve(K,A)
#     s2 = naive(K,A)
#     if s1 != s2:
#         print(n)
#         print(K)
#         print(A)
#         print(s1)
#         print(s2)
#         exit()
# solve(2,[1,1,1])

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

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import defaultdict
from bisect import bisect_left

n, k = li()
a = list(li())

a = a + a

# ジャンプ先
jump = defaultdict(lambda: -1)
buf = defaultdict(lambda: -1)
for i, ai in enumerate(a):
    if buf[ai] != -1:
        jump[buf[ai]] = i - buf[ai]

    buf[ai] = i

# 周期を求める
checkpoint = [0]
cur = 0

while cur == 0 or cur % n > 0:
    cur += jump[cur % n]
    cur += 1
    checkpoint.append(cur)

cycle = cur // n
mod = k % cycle

# あまり処理
if mod == 0:
    print()

else:
    last_idx = n * mod

    # シミュレーション
    start_idx = checkpoint[bisect_left(checkpoint, last_idx) - 1]
    s = []

    idx = start_idx
    while idx < last_idx:
        if idx + jump[idx % n] < last_idx:
            idx += jump[idx % n] + 1
        else:
            s.append(a[idx % n])
            idx += 1

    print(*s)

Submission status: Accepted

Solution code:
import bisect
n, k = map(int, input().split())
alist = list(map(int, input().split()))
positions = [[] for i in range(200002)]
for i in range(n):
    positions[alist[i]].append(i)
visited = [0] * n
lastList = []
nextP = 0
times =0
while True:
    num = alist[nextP]
    if len(positions[num]) == 1:
        lastList.append(nextP)
        visited[nextP] = times
        times += 1
        nextP += 1
        if nextP == n:
            break
    else:
        nextIn = bisect.bisect_right(positions[num], nextP)
        if nextIn == len(positions[num]):
            lastList.append(nextP)
            visited[nextP] = times
            times += 1
            nextP = positions[num][0] + 1
        else:
            nextP = positions[num][nextIn] + 1
            if nextP == n:
                break
if times != 0:
    loopIn = k % (times + 1)
    if loopIn != 0:
        loopIn -= 1
        lastIn = lastList[loopIn]
        result = []
        while True:
            num = alist[lastIn]
            nextIn = bisect.bisect_right(positions[num], lastIn)
            if nextIn == len(positions[num]):
                result.append(num)
                lastIn += 1
            else:
                lastIn = positions[num][nextIn] + 1
            if lastIn == n:
                break
        if len(result) > 0:
            print(' '.join(map(str, result)))

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    idx = [[] for _ in range(int(2e5+1))]
    for i in range(N):
        idx[A[i]].append(i)
    pos = 0
    empty = []
    visited = set()
    while pos == 0 or pos % N != 0:
        empty.append(pos)
        visited.add(pos % N)
        a = A[pos % N]
        nxt = bisect_right(idx[a], pos % N) % len(idx[a])
        npos = idx[a][nxt] + (pos//N) * N
        if npos <= pos:
            npos += N
        pos = npos + 1
    goal = N * K % pos
    cur = empty[max(0, bisect_right(empty, goal) - 1)]
    #print(cur, goal)
    ans = []
    seen = set()
    while cur < goal:
        i = cur % N
        a = A[i]
        nxt = bisect_right(idx[a], cur % N) % len(idx[a])
        ncur = idx[a][nxt] + (cur//N) * N
        if ncur <= cur:
            ncur += N
        if ncur < goal:
            cur = ncur + 1
        else:
            ans += [a]
            cur = cur + 1
    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    B = [None]*N
    firstPos = {}
    lastPos = {}

    for p, a in enumerate(A):
        if a in lastPos:
            B[lastPos[a]] = p
            B[p] = firstPos[a]
        else:
            firstPos[a] = p
            B[p] = p

        lastPos[a] = p

    C = [None]*N
    for p, b in enumerate(B):
        c = (b - p)%N
        if c == 0:
            c = N

        C[p] = c + 1

    cycle = C[0]
    nextPos = cycle%N

    while nextPos != 0:
        cycle += C[nextPos]
        nextPos = (nextPos + C[nextPos])%N

    r = N*K%cycle
    ans = []

    while r > 0:
        while r >= C[(-r)%N]:
            r -= C[(-r)%N]

        if r > 0:
            ans.append(A[(-r)%N])
            r -= 1
        
    print(' '.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
n, k = map(int, input().split())
a = list(map(int, input().split()))
if n == 1:
	if k%2 == 1:
		print(a[0])
	else:
		print("")
else:
	aa = a + a
	skip = [0 for _ in range(n)]
	ind = dict()
	for i in range(2*n-1, -1, -1):
		if aa[i] in ind and i < n:
			skip[i] = ind[aa[i]]-i+1
		ind[aa[i]] = i
	#print(skip)
	if k == 1:
		ans = []
		cnt = 0
		while cnt < n:
			if cnt + skip[cnt%n] > n:
				ans.append(a[cnt])
				cnt += 1
			elif cnt + skip[cnt%n] <= n:
				cnt += skip[cnt%n]
		print(*ans)
		sys.exit()
	cnt = 0
	while cnt == 0 or (cnt + skip[cnt%n] <= n*k and cnt%n != 0):
		cnt += skip[cnt%n]
	if cnt%n == 0:
		l = cnt//n
		#print(l)
		k %= l
		if k == 0:
			print("")
			sys.exit()
		cnt = 0
		while cnt == 0 or cnt + skip[cnt%n] <= n*k:
			cnt += skip[cnt%n]
	ans = []
	cnt = cnt%n
	while cnt < n:
		if cnt + skip[cnt%n] > n:
			ans.append(a[cnt])
			cnt += 1
		elif cnt + skip[cnt%n] <= n:
			cnt += skip[cnt%n]
	print(*ans)

Submission status: Accepted

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

dict = {}
A_set = set(A)
for a in A_set:
    dict[a] = []
for i in range(N):
    dict[A[i]].append(i)

trans = {}
for a_list in dict.values():
    for i in range(len(a_list)):
        trans[a_list[i - 1]] = a_list[i]

k = 1
pos = 0
print_ans = 0
div_flag = 0
while True:
    new_pos = trans[pos]
    if new_pos <= pos:
        if k + 1 <= K:
            k += 1
            if new_pos + 1 < N:
                pos = new_pos + 1
            else:
                if div_flag == 0:
                    pos = 0
                    K = K % k
                    k = 1
                    div_flag = 1
                else:
                    print('')
                    break
        else:
            print_ans = 1
            break
    else:
        if new_pos + 1 < N:
            pos = new_pos + 1
        else:
            if div_flag == 0:
                pos = 0
                K = K % k
                k = 1
                div_flag = 1
            else:
                print('')
                break

if print_ans:
    ans = []
    i = pos
    while i < N:
        if trans[i] <= i:
            ans.append(A[i])
            i += 1
        else:
            i = trans[i] + 1
    print(' '.join(map(str, ans)))