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 = map(int, input().split())
A = list(map(int, input().split()))

# first : 数列Aのi番目以降の要素で操作をしたときに残っている最初の数字
#   first[idx] > 0  => idxからスタート
#   first[idx] == 0 => 空の数列が残る
#   first[idx] < 0  => follow_idx[idx]からスタート(後々スタートの数だけ取り出したいため区別して負の数で保持)
# follow_idx : 数列Aのi番目以降の要素で操作をしたときに残っている次の数のindex
first = [0] * (N+1)
follow_idx = [-1] * (N+1)
# d : ある数字が出現したindexを記憶
d = {}
for i, a in enumerate(A[::-1]):
  j = N - 1 - i
  # 自分よりも後に自分と同じ数字が出現する場合、その位置まで消えて、その次からスタートしたときと同じものが残る
  if a in d:
    idx = d[a][-1] + 1 # j以降にaと同じ数字が出現するindexの中で最も近いもの次のindex
    d[a].append(j)
    if first[idx] < 0: # 負の数 => idx番目の数からスタートしない
      first[j] = first[idx] # 自身から始まらないため、ここも負の数のまま保持
      follow_idx[j] = follow_idx[idx] # 本当に始まるindexを記録
    else: # 正の数 => idx番目からスタートする
      first[j] = -first[idx] # 自身から始まらないため、負の数で保持
      follow_idx[j] = idx # 本当はidxから始まる
  
  # 自分よりも後に自分と同じ数字が出現しない場合、先頭に自身を追加して、一つ後ろからスタートしたときと同じものが残る
  else:
    first[j] = a # 自身からスタート
    d[a] = [j]
    follow_idx[j] = j + 1 # 自身の次は一つ後ろにつながる


# indices : 先頭の数字が元の数列でどのindexだったかを記録
indices = [-1] # ダミー
s0 = first[0] # 数列を1つだけ並べて操作を行ったときに残る先頭の数字
if s0 >= 0: 
  indices.append(0) # 0以上の場合、自身から始まる
else:
  s0 = -s0 # 負の場合、正の値に戻す
  indices.append(follow_idx[0]) # 自身から始まるわけではないので、本当に始まるindexを追加

if s0 == 0: # 数列を1つ並べて操作を行った後の数列が空 => 何個並べても最終的に空になる
  print('')
  quit()

# first_a : 先頭の数字として出現したものを記録
#   key : 先頭の数字
#   value : 数列Aを何個並べて操作を行った場合か
first_a = {0:0, s0:1}
for k in range(2, K+1):
  idx = d[s0][-1] + 1 # 先頭の数字が最初に現れるとそこまで消えて、その次からスタートする
  s0 = first[idx] # 上で求めたスタート位置から始めたときに残る数列の先頭の数字
  if s0 >= 0: # 0以上ならその数字自身から始まる
    indices.append(idx) # ので、idxをそのまま記録
  else: # 負の数なら、本当はその位置から始まるわけではない
    s0 = -s0 # 一旦、正の値に戻しておく
    indices.append(follow_idx[idx]) # 本当のスタート位置を記録
  if s0 in first_a: # 既にその数からスタートしたことがある => ここから先は周期的に振る舞う
    break
  first_a[s0] = k # s0が先頭となるkを記録しておく

if len(indices) < K: # 周期を発見してシミュレーションが終了した場合、Kを更新
  # 1, 2, ..., first_a[s0], ..., k
  # ?, ?, ..., s0,          ..., s0
  #              <------------->
  #                 ここが周期
  K = first_a[s0] + (K - first_a[s0]) % (k - first_a[s0])

if K == 0: # 丁度からの数列になったときに終了している
  print('')
  quit()

ans = []
idx = indices[K] # ここからスタートしたときに残る数列と同じものが残る
while idx < N: # 最後尾になるまで後ろ側に辿っていく
  s = first[idx]
  if s > 0: # 正で保持されているなら、その数字を使うということなのでansに追加
    ans.append(s)
  idx = follow_idx[idx]

print(*ans)

Submission status: Accepted

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

first = [0] * (N+1)
follow_idx = [-1] * (N+1)
d = {}
for i, a in enumerate(A[::-1]):
  j = N - 1 - i
  if a in d:
    idx = d[a][-1]
    d[a].append(j)
    if first[idx + 1] < 0:
      first[j] = first[idx + 1]
      follow_idx[j] = follow_idx[idx + 1]
    else:
      first[j] = -first[idx + 1]
      follow_idx[j] = idx + 1
  else:
    first[j] = a
    d[a] = [j]
    follow_idx[j] = j + 1


indices = [-1]
s0 = first[0]
if s0 >= 0:
  indices.append(0)
else:
  s0 = -s0
  indices.append(follow_idx[0])
    
if s0 == 0:
  print('')
  quit()

d2 = {0:0, s0:1}
for k in range(2, K+1):
  idx = d[s0][-1] + 1
  s0 = first[idx]
  if s0 >= 0:
    indices.append(idx)
  else:
    s0 = -s0
    indices.append(follow_idx[idx])
  if s0 in d2:
    break
  d2[s0] = k

if len(indices) < K:
  K = d2[s0] + (K - d2[s0]) % (k - d2[s0])

if K == 0:
  print('')
  quit()

ans = []
idx = indices[K]
while idx < N:
  s = first[idx]
  if s > 0:
    ans.append(s)
  idx = follow_idx[idx]

print(*ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from collections import defaultdict
from bisect import bisect_right

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# Aの中で次に同じ数字が出てくるindex
N, K = lr()
A = lr()
next_index = [-1] * N
dict = defaultdict(list)
for i in range(N):
    dict[A[i]].append(i)

for i in range(N):
    a = A[i]
    length = len(dict[a])
    j = bisect_right(dict[a], i)
    next_index[i] = dict[a][j%length]

cur = 0
time = 1
while cur != N:
    ne = next_index[cur]
    if ne <= cur:
        time += 1
    cur = ne + 1
# timeで一周する
K %= time
time = 0
cur = 0
while time < K:
    ne = next_index[cur]
    if ne <= cur:
        time += 1
    if time == K:
        break
    cur = ne + 1

answer = []
while cur < N:
    ne = next_index[cur]
    if ne <= cur:
        answer.append(A[cur])
        cur += 1
    else:
        cur = ne + 1

print(*answer)
# 14

Submission status: Accepted

Solution code:
from collections import deque


def solve(i):
    if i in memo:
        return memo[i]
    q = deque([i])
    while True:
        nxt_i = next_ind[i]
        if nxt_i >= n:
            break
        q.append(nxt_i)
        i = nxt_i
    while q:
        memo[q.pop()] = nxt_i % n
    return memo[i]



n, k = map(int, input().split())
a = list(map(int, input().split())) + [-1, -1]
k_time = k
n += 2
aa = a + a
next_ind = [-1] * (2 * n)
tmp_memo = {}
for i in range(2 * n)[::-1]:
    if aa[i] not in tmp_memo:
        tmp_memo[aa[i]] = i + 1
    else:
        next_ind[i] = tmp_memo[aa[i]]
        tmp_memo[aa[i]] = i + 1

log_size = k.bit_length() + 2
double = [[-1] * n for i in range(log_size)]

# ダブリングで2^0回(= 1回)たどって到達する値を求める
memo = {}
for i in range(n):
    double[0][i] = solve(i)

# ダブリングで2^k回たどって到達する値を求める
for k in range(1, log_size):
    for i in range(n):
        double[k][i] = double[k - 1][double[k - 1][i]]

pos = 0
k_time -= 1
for k in range(log_size):
    if (k_time >> k) & 1:
        pos = double[k][pos]
q = deque([])
set_ = set()
for i in range(pos, n):
    if a[i] not in set_:
        set_.add(a[i])
        q.append(a[i])
    else:
        while True:
            tmp = q.pop()
            set_.remove(tmp)
            if tmp == a[i]:
                break
print(*q)

Submission status: Accepted

Solution code:
"""
iの直前で空のときに、Xi=Xj(i<j)であるようなjまで進むと、空になる
よってnext[i] = j
iの直前に空のときに、次にiの直前で空が回ってくるまでのidxの変化
jump[i] = ? * N or inf
もしjump[i] != infならできるだけこれを回したあとに、愚直にやるだけでよい
もしjump[i] == infならnext[i]に移動して、これを試す
どこかで周期ができるはずなので鳩ノ巣原理よりO(N)で見つかる
"""

#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K=MI()
    A=LI()
    A *= 2 #2周分
    next_ = [-1]*2*N #次同じ数字が現れるidx
    last = defaultdict(lambda : -1) #各数字の現時点での最後尾
    for i,a in enumerate(A):
        if last[a] != -1:
            next_[last[a]] = i
        last[a] = i
    
    now = 0 #今のidx(mod N)
    accumulate_step = 0 #累計
    step_size = 0 #周期サイズ
    last_step = [-1]*2*N #そのidxに来たときのaccumulate_step
    #このwhileでは空の状態で進んでいく
    while accumulate_step + next_[now] - now  < N*K: #ぎりぎりまでnextやstep_sizeでたどる
        if last_step[now]!=-1: #周期があった!
            step_size = accumulate_step - last_step[now]
            remain = N*K - accumulate_step
            accumulate_step += remain//step_size * step_size
            now = accumulate_step%N
            if remain//step_size: #無限ループ回避
                continue
        
        #普通にnext_をたどって1個進む
        last_step[now] = accumulate_step
        before = now 
        now = next_[before] + 1
        accumulate_step += now - before 
        now %= N
    
    #残りはnaiveにやる
    remain = N*K-accumulate_step
    ans = []
    cnt = defaultdict(int)
    for a in A[2*N-remain:]:
        if not cnt[a]:
            ans.append(a)
            cnt[a] += 1
            continue
        while cnt[a]:
            cnt[ans.pop()] -= 1
    print(*ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
iの直前で空のときに、Xi=Xj(i<j)であるようなjまで進むと、空になる
よってnext[i] = j
iの直前に空のときに、次にiの直前で空が回ってくるまでのidxの変化
jump[i] = ? * N or inf
もしjump[i] != infならできるだけこれを回したあとに、愚直にやるだけでよい
もしjump[i] == infならnext[i]に移動して、これを試す
どこかで周期ができるはずなので鳩ノ巣原理よりO(N)で見つかる
"""

#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K=MI()
    A=LI()
    A *= 2 #2周分
    next_ = [-1]*2*N
    last = defaultdict(lambda : -1)
    for i,a in enumerate(A):
        if last[a] != -1:
            next_[last[a]] = i
        last[a] = i
    
    now = 0
    accumulate_step = 0
    step_size = 0
    last_step = [-1]*2*N
    while accumulate_step + next_[now] - now  < N*K:
        if last_step[now]!=-1:
            step_size = accumulate_step - last_step[now]
            remain = N*K - accumulate_step
            accumulate_step += remain//step_size * step_size
            now = accumulate_step%N
            if remain//step_size:
                continue
        
        last_step[now] = accumulate_step
        before = now 
        now = next_[before] + 1
        accumulate_step += now - before 
        now %= N
    
    remain = N*K-accumulate_step
    ans = []
    cnt = defaultdict(int)
    for a in A[2*N-remain:]:
        if not cnt[a]:
            ans.append(a)
            cnt[a] += 1
            continue
        while cnt[a]:
            cnt[ans.pop()] -= 1
    print(*ans)

    # seq = []
    # remain = -1
    # if step_size == 0:#愚直に試す
    #     remain = N*K - accumulate_step 
    #     seq = []
    #     if remain%N:
    #         seq.extend(A[-(remain%N)])
    #     seq.extend(A[:N] * (remain//N))
    #     for a in seq:
    #         if not cnt[a]:
    #             cnt[a] += 1
    #             ans.append(a)
    #             continue
    #         while cnt[a]:
    #             cnt[ans.pop()]-=1

    #     print(*ans)
    #     return 
    # else:
    #     remain = N*K - accumulate_step
    #     remain %= step_size

    #     # print(N*K , accumulate_step, step_size, remain)
    # # print(remain)
    # ans = []
    # cnt = defaultdict(int)
    # # print(A[-(remain%N):] , A[:N]*(remain//N))
    # print(A,-(remain%N))


    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = a + a
to = [-1] * n
num = [-1] * (2 * 10 ** 5 + 1)
for i, x in enumerate(b):
    if 0 <= num[x] < n:
        to[num[x]] = i + 1
    num[x] = i

c, now = 1, 0
check = 0
while now != n:
    v = to[now]
    if v > n:
        c += 1
        v -= n

    now = v



k %= c
now = 0
while k > 1:
    v = to[now]
    if v > n:
        k -= 1
        v -= n

    now = v

ans = []

while now < n:
    if to[now] < n:
        now = to[now]
    elif to[now] == n:
        break
    else:
        ans.append(a[now])
        now += 1

print(*ans)

Submission status: Accepted

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

N, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
L = [0]*N
P = [-1]*(2*10**5+1)
for i in range(2*N):
    j = i%N
    a = A[j]
    if P[a] == -1:
        P[a] = i
    else:
        L[P[a]] = j
        P[a] = j
s = 0
start = 0
v = [True]*N
h = [(0, 0)]
h_app = h.append
while v[start]:
    v[start] = False
    if start < L[start]:
        s += (L[start] - start +1)
    else:
        s += (L[start] - start +N +1)
    start = (L[start]+1)%N
    h_app((s, start))

r = (N*K)%s
import bisect
if r == 0:
    print("")
else:
    res = bisect.bisect(h, (r, 10**10))-1
    s, start = h[res]
    s = r-s
    ans = []
    P = [-1]*(2*10**5+1)
    if s:
        cou = 0
        for i in range(s):
            if P[A[(start+i)%N]] == -1:
                P[A[(start+i)%N]] = cou
                ans.append(str(A[(start+i)%N]))
            else:
                sr = P[A[(start+i)%N]]
                P[A[(start+i)%N]] = -1
                for j in range(cou-sr):
                    a = ans.pop()
                    P[int(a)] = -1
                cou = sr-1
            cou += 1
    print(" ".join(ans))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from bisect import bisect_right

N,K = LI()
A = LI()

# 各値の場所
d = defaultdict(list)
for i in range(N):
    d[A[i]].append(i)

# 各場所スタートでの，終了時の先頭要素
T = [0]*(N+1)
for i in range(N)[::-1]:
    p = bisect_right(d[A[i]],i)
    if p < len(d[A[i]]):
        T[i] = T[d[A[i]][p]+1]
    else:
        T[i] = A[i]

# 各indexスタートが何週目の操作で起こるか
S = defaultdict(list)
index = 0
roop_flag = False
empty_flag = False
for i in range(1,N+2):
    S[index].append(i)
    if len(S[index]) > 1:
        start = S[index][0]
        end = S[index][1]
        roop_flag = True
        break
    n = T[index]
    if n == 0:
        num = i
        empty_flag = True
        break
    index = d[n][0]+1

def request_s(index):
    ret = []
    while index <= N-1:
        p = bisect_right(d[A[index]],index)
        if p < len(d[A[index]]):
            index = d[A[index]][p]+1
        else:
            ret.append(A[index])
            index += 1
    return ret

if roop_flag:
    if K <= start:
        index = 0
        for i in range(K-1):
            index = d[T[index]][0]+1
        ans = request_s(index)
    else:
        index = 0
        for i in range(start-1):
            index = d[T[index]][0]+1
        left = (K-(start-1)) % (end-start+1)
        if left == 0:
            left = end-start+1
        for i in range(left-1):
            index = d[T[index]][0]+1
        ans = request_s(index)
else:
    K = K%num
    index = 0
    if K == 0:
        ans = []
    else:
        for i in range(K-1):
            index = d[T[index]][0]+1
        ans = request_s(index)

print(*ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import defaultdict
N, K, *A = map(int, open(0).read().split())
dic = defaultdict(list)
for i, a in enumerate(A):
  dic[a] += [i]
ls = []
ps = 0
m = A[0]
cycle = 0
while True:
  ls.append(ps+N*cycle+1)
  i = bisect_left(dic[m],ps+1)
  ps = dic[m][i%len(dic[m])]
  if i>=len(dic[m]):
    cycle += 1
  ps += 1
  ps %= N
  m = A[ps]
  if ps==0:
    cycle += 1
    break
k = K%cycle
j = bisect_left(ls,k*N)
if ls[j]==k*N:
  c = (ls[j]-1)%N
  print(A[c])
elif ls[j]==k*N+1:
  pass
else:
  c = (ls[j-1]-1)%N
  M = k*N-ls[j-1]
  ans = [A[c]]
  log = set(ans)
  ind = {}
  ind[A[c]] = 0
  cnt = 0
  while M:
    c += 1
    c %= N
    cnt += 1
    cnt %= N
    M -= 1
    if not A[c] in log:
      log.add(A[c])
      ind[A[c]] = cnt
      ans += [A[c]]
    else:
      log.remove(A[c])
      ans = ans[:ind[A[c]]]
      log = set(ans)
      cnt = ind[A[c]]-1
  print(*ans)

Submission status: Accepted

Solution code:
#17:43
n,k = map(int,input().split())
a = list(map(lambda x: int(x)-1, input().split()))
mx = max(a) + 1
num = [[] for _ in range(mx)]
leg = [0 for _ in range(mx)]
for i in range(n):
  num[a[i]].append(i)
  leg[a[i]] += 1
#print(num)
nex = [0 for _ in range(n)]
for j in range(mx):
  nu = num[j]
  le = leg[j]
  for li in range(le-1):
    nex[nu[li]] = nu[li+1]+1
  if nu:
    nex[nu[-1]] = nu[0]+n+1
#print(nex)
unit = 0
now = 0
while True:
  tmp = nex[now]
  unit += tmp // n
  now = tmp % n
  #print(tmp,now)
  if now == 0:
    break
#print(unit)
k %= unit
k *= n
#print(k)
if k == 0:
  exit()
while True:
  tmp = nex[now]
  if k - (tmp-now) > 0:
    k -= tmp - now
    now = tmp % n
  else:
    ans = a[-k:]
    break
  #print(k)
l = len(ans)
seen = [0 for _ in range(mx)]
ans2 = []
for li in range(l):
  if seen[ans[li]] == 1:
    while True:
      p = ans2.pop()
      seen[p] = 0
      if p == ans[li]:
        break
  else:
    ans2.append(ans[li])
    seen[ans[li]] = 1
print(' '.join(map(lambda x:str(x+1),ans2)))

Submission status: Accepted

Solution code:
from bisect import bisect_right
import sys
N, K = map(int, input().split())
A = list(map(int, input().split()))
a_to_i = [[] for _ in range(max(A)+1)]
for i in range(N):
    a_to_i[A[i]].append(i)
next_index = [-1]*N
for i in range(N):
    a = A[i]
    j = bisect_right(a_to_i[a], i)
    if j == len(a_to_i[a]):
        next_index[i] = a_to_i[a][0]+N
    else: next_index[i] = a_to_i[a][j]
now = 0
cnt = 0
while True:
    i = next_index[now]
    if i>=N:
        i%=N
        cnt+=1
    else: now = i
    i+=1
    if i>=N:
        cnt+=1
        i%=N
    now = i
    if now == 0:
        break
K%=cnt
if K==0:
    print()
    sys.exit()
ans = [A[0]]
K*=N
K-=1
now = 0
while now<K:
    ni = next_index[now%N]+1
    if(now//N)*N+ni-1 == K:
        ans.pop()
        break
    if (now//N)*N+ni>K:
        now+=1
        ans.append(A[now%N])
    else:
        now = (now//N)*N+ni
        ans[-1] = A[now%N]




print(*ans, sep = ' ')

Submission status: Accepted

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

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

AA = A+A
last_i = {}
nx = [-1]*N
for i,a in enumerate(reversed(AA)):
    i = 2*N-i-1
    if i < N:
        nx[i] = (last_i[a] - i) % N + 1
    last_i[a] = i

visited = [-1]*N
visited[0] = 0
j = i = 0
while 1:
    p = nx[i]+N if nx[i]==1 else nx[i]
    j += p
    if visited[j%N] < 0:
        visited[j%N] = j
    else:
        break
    i = j%N
cycle = (j - visited[j%N]) // N
K %= cycle
j = i = 0
while 1:
    p = nx[i]+N if nx[i]==1 else nx[i]
    if j+p > N*K:
        break
    j += p
    i = j%N

if j%N == 0:
    if K==1:
        print(*A)
    else:
        print()
else:
    ans = []
    anss = set()
    for a in A[j%N:]:
        if a in anss:
            while ans[-1] != a:
                anss.remove(ans[-1])
                ans.pop()
            anss.remove(a)
            ans.pop()
        else:
            anss.add(a)
            ans.append(a)
    print(*ans)

Submission status: Accepted

Solution code:
import bisect
from collections import defaultdict
n,k = map(int,input().split())
a = list(map(int,input().split()))
dc = defaultdict(int)
for i in range(n):
  if dc[a[i]]:
    dc[a[i]].append(i)
  else:
    dc[a[i]] = [i]
p = 0
cnt = 1
dcp = defaultdict(int)
while p != n and cnt<k:
  x = a[p]
  if p == dc[x][-1]:
    p = dc[x][0]+1
    cnt += 1
    dcp[cnt] = p
  else:
    q = bisect.bisect_right(dc[x],p)
    p = dc[x][q]+1
if cnt<k:
  k = k%cnt
ans = []
pos = dcp[k]
flg = [0 for i in range(200000+1)]
for i in range(pos,n):
  if flg[a[i]] == 0:
    ans.append(a[i])
    flg[a[i]] = 1
  else:
    while ans[-1] != a[i]:
      t = ans.pop()
      flg[t] = 0
    ans.pop()
    flg[a[i]] = 0
print(*ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
dp = [0] * (N + 1)
d = dd(list)
for i in range(N):
  d[a[i]].append(i)
for i in range(N - 1, -1, -1):
  j = bl(d[a[i]], i)
  if j == len(d[a[i]]) - 1:
    dp[i] = a[i]
  else:
    dp[i] = dp[d[a[i]][j + 1] + 1]
p = dp[0]
t = 1
l = [0, dp[0]]
if l[-1] == 0:
  t -= 1
  l.pop()
d[0].append(-1)
for _ in range(N):
  p = dp[d[p][0] + 1]
  t += 1
  if p == 0: break
  l.append(p)
p = l[(K - 1) % t]
i = d[p][0] + 1
res = []
while i < N:
  j = bl(d[a[i]], i)
  if j < len(d[a[i]]) - 1:
    i = d[a[i]][j + 1]
  else:
    res.append(a[i])
  i += 1
print(*res)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
dp = [0] * (N + 1)
d = dd(list)
for i in range(N): d[a[i]].append(i)
for i in range(N - 1, -1, -1):
  j = bl(d[a[i]], i)
  if len(d[a[i]]) - 1 > j: dp[i] = dp[d[a[i]][j + 1] + 1]
  else: dp[i] = a[i]
res = [0, dp[0]]
d[0].append(-1)
#print(dp)
if dp[0] == 0: res.pop()
while dp[d[res[-1]][0] + 1] > 0:
  res.append(dp[d[res[-1]][0] + 1])
  #print(res, i)
#print(res)
#print((K - 1) % len(res))
if K % len(res) == 0:
  print()
  exit(0)
rres = []
i = d[res[(K - 1) % len(res)]][0] + 1
while i < N:
  j = bl(d[a[i]], i)
  if len(d[a[i]]) - 1 > j: i = d[a[i]][j + 1] + 1
  else:
    rres.append(a[i])
    i += 1
print(*rres)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, A):

    d = defaultdict(list)
    for i, a in enumerate(A):
        d[a].append(i)

    ni = []
    for i, a in enumerate(A):
         ni.append(d[a][bisect.bisect_right(d[a], i) % len(d[a])])

    i = 0
    k = 1
    while True:
        j = ni[i]
        if j <= i:
            k +=1
        i = (j + 1) % N

        if i == 0:
            break

    error_print(k, K % k)
    s = []
    ss = set()

    i = 0
    K %= k
    k = 0
    while k < (K-1):
        j = ni[i % N]
        if j <= i:
            k += 1
        i = j + 1

    i += k * N
    s = []
    ss = set()
    for l in range(i, N*K):
        m = l % N
        a = A[m]
        if a in ss:
            while True:
                b = s.pop()
                ss.remove(b)
                if b == a:
                    break
        else:
            s.append(a)
            ss.add(a)
    return ' '.join(map(str, s))


def main():
    N, K = read_int_n()
    A = read_int_n()
    print(slv(N, K, A))

    # N = 2*(10**5)
    # # N = 10
    # K = 10**12
    # A = [random.randint(1, N) for _ in range(N)]
    # # print(A)
    # print(slv(N, K, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
from bisect import bisect_left,bisect
import sys

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

A_max=max(A)
lst=[[] for i in range(A_max+1)]
flag=[0]*(A_max+1)
for i in range(n):
    lst[A[i]].append(i)

flag=[0]*n
data=[]
i=0
while flag[i]==0:
    flag[i]=1
    a=A[i]
    b=bisect(lst[a],i)
    if b==len(lst[a]):
        data.append(i)
        i=lst[a][0]+1
    else:
        i=lst[a][b]+1
    if i==n:
        data.append(n)
        i=0

#大丈夫
if not data:
    print()
    sys.exit()
s=len(data)
zzz=data[(K-1)%s]
i=zzz
d=[]
while i<n:
    a=A[i]
    b=bisect(lst[a],i)
    if b<len(lst[a]):
        d.append([i,lst[a][b]])
        i=lst[a][b]+1
        continue
    else:
        i+=1


if d:
    ans=A[zzz:d[0][0]]
    for j in range(len(d)-1):
        ans=list(itertools.chain(ans,A[d[j][1]+1:d[j+1][0]]))
    ans=list(itertools.chain(ans,A[d[-1][1]+1:]))
    print(*ans)
else:
    print(*A[zzz:])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    idx=[[] for _ in range(max(A)+1)]
    for i,a in enumerate(A):
        idx[a].append(i)

    # いくつ先に移動するかを求める
    next=[None]*n
    for I in idx:
        if(not I): continue
        s=len(I)
        I.append(I[0]+n)
        for i in range(s):
            next[I[i]]=I[i+1]-I[i]+1

    # doubling
    M=10**18 # n*k より大きな数で抑えておく
    nexts=[next]
    for _ in range(60):
        next=nexts[-1]
        nnext=[min(M,next[i]+next[(i+next[i])%n]) for i in range(n)]
        nexts.append(nnext)

    now=0
    for next in nexts[::-1]:
        if(now+next[now%n]<=n*k):
            now+=next[now%n]
    if(now==n*k):
        return

    # A[now%n:] に対してシミュレーションする
    ans=[]
    have=[0]*(max(A)+1)
    for a in A[now%n:]:
        if(not have[a]):
            ans.append(a)
            have[a]=1
        else:
            while(1):
                x=ans.pop()
                have[x]=0
                if(x==a): break

    print(*ans)
resolve()

Submission status: Accepted

Solution code:
def main():
    import bisect
    n,k=map(int,input().split())
    x=list(map(int,input().split()))
    d=dict()
    for j,i in enumerate(x):
        if i in d.keys():
            d[i].append(j)
        else:
            d[i]=[j]
    first_word=[""]
    
    def operation(temp_operated,temp_operator):
        l=[i for i in temp_operated]
        s=set(temp_operated)
        for i in temp_operator:
            if i in s:
                while True:
                    if l[-1]!=i:
                        l.pop()
                    else:
                        l.pop()
                        s=set(l)
                        break
            else:
                l.append(i)
                s.add(i)
        return l
    
    if operation("",x)!=[]:
        first_word.append(operation("",x)[0])
    flag=0

    while True:
        w=first_word[-1]
        if w=="":
            break
        t=d[w][0]
        if t==n-1:
            break
        while True:
            ww=x[t+1]
            temp=bisect.bisect_right(d[ww],t+1)
            if temp>=len(d[ww]):
                first_word.append(ww)
                break
            else:
                t=d[ww][temp]
                if t==n-1:
                    flag=1
                    break
        if flag==1:
            break
    
    l=len(first_word)
    k=k%l
    if len(first_word)==1:
        print("")
    elif k-1==0:
        print(*operation("",x))
    else:
        print(*operation("",x[d[first_word[k-1]][0]+1:]))

main()

Submission status: Accepted

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

# In[1]:


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


# In[2]:


kioku = {}
saisyo = {}
idou = {}

for i in range(N):
    if A[i] in kioku:
        idou[kioku.pop(A[i])] = i
    kioku[A[i]] = i
    if A[i] not in saisyo:
        saisyo[A[i]] = i

    


# In[3]:


# kioku


# In[4]:


# saisyo


# In[5]:


# idou


# In[6]:


i = 0
ret = []
while True:
    if i in idou:
        i = idou[i]
    else:
        ret.append(i)
        i = saisyo[A[i]]
    if i == N - 1:
        i = 0
        break
    else:
        i += 1


# In[7]:


# 3-35 -59- -92- -26- -65-5 31415926535


# In[8]:


# ret


# In[ ]:





# In[ ]:





# In[9]:


loop = len(ret) + 1
if K % loop != 0:
#     print(ret[K % loop - 1])
#     print(A[ret[K % loop - 1]:])
    i = ret[K % loop - 1]
    ans = []
    while i <= N - 1:
        if i in idou:
            i = idou[i]
        else:
            ans.append(A[i])
        i += 1
    print(' '.join(map(str, ans)))


# In[ ]:

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
l,r,*b=[[]for _ in range(10**6)]
for i,v in enumerate(a):
  b[v]+=i,
  l+=len(b[v]),
s=a[0]
i=c=0
while 1:
  j=l[i]%len(b[s])
  if(c>k-2)>j:
    r+=s,
    i+=1
  else:i=b[s][j]+1
  c+=j<1
  if i==n:
    if c>k-2:break
    k%=c+1
    i=c=0
  s=a[i]
print(*r)