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()))
aa=a+a
lp=[-1]*n
dn={}
for i in range(2*n):
    x=aa[i]
    if x in dn:
        dn[x].append(i)
    else:
        dn[x]=[i]
from bisect import bisect_right,bisect_left
now_idx=0
ka=set(())
cnt=1
while True:
    v=a[now_idx]
    tmp=bisect_right(dn[v],now_idx)
    next_idx=dn[v][tmp]
    if next_idx>=n:
        cnt+=1
        next_idx%=n
    if next_idx in ka:
        break
    ka.add(next_idx)
    lp[next_idx]=cnt
    now_idx=next_idx+1
    now_idx%=n
ml=max(lp)
k%=ml
ans=[]
#print(lp,k)
c=set(())
for i in range(n):
    if lp[-1-i]==-1 or lp[-1-i]%ml!=k:
        ans.append(str(a[-1-i]))
    else:
        break
ans.reverse()
dnn={}
m=len(ans)
for i in range(m):
    if ans[i] in dnn:
        dnn[ans[i]].append(i)
    else:
        dnn[ans[i]]=[i]
aans=[]
i=0
while i<m:
    tmp=bisect_right(dnn[ans[i]],i)
    if tmp==len(dnn[ans[i]]):
        aans.append(ans[i])
        i+=1
    else:
        i=dnn[ans[i]][tmp]+1
print(' '.join(aans))

Submission status: Accepted

Solution code:
import bisect
N, K, *A = [int(_) for _ in open(0).read().split()]
K -= 1
L = [[] for _ in range(2 * 10**5 + 1)]
for i, a in enumerate(A * 2):
    L[a] += [i]
before_next = [L[a][bisect.bisect(L[a], i)] for i, a in enumerate(A)]
first_cycle = [None] * N
now = 0
idx = 0
cycle = 0
while True:
    if first_cycle[now] is not None:
        break
    first_cycle[now] = cycle
    now = before_next[now] + 1
    dcycle, now = divmod(now, N)
    cycle += dcycle
cycle2 = cycle
cycle1 = first_cycle[now]
#K cycle目=cycle1+(K-cycle1)%(cycle2-cycle1) cycle目
K2 = cycle1 + (K - cycle1) % (cycle2 - cycle1)
if K2:
    f1 = f2 = 0
    for i in range(N - 1, -1, -1):
        if first_cycle[i] == K2 - 1:
            f1 = 1
            break
    for j in range(N - 1, -1, -1):
        if first_cycle[j] == K2:
            f2 = 1
            break
    if f2:
        B = A[j:]
    elif f1:
        B = A[i:] + A
else:
    B = A
ans = []
cnt = [0] * (2 * 10**5 + 1)
for a in B:
    if cnt[a] > 0:
        while True:
            cnt[ans.pop()] -= 1
            if cnt[a] == 0:
                break
    else:
        ans += [a]
        cnt[a] += 1
print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
a = inl()

# nxt loc for each val
prev = [-1]*200001
nxt = [-1]*(n+1)
for i in range(2*n):
    v = a[i%n]
    if 0<=prev[v]<n:
        nxt[prev[v]] = (i+1)%n
    prev[v] = i
#ddprint("nxt")
#ddprint(nxt)

# find loop
last = [-1]*(2*n)
cur = 0
cyc = 0
dolast = False
for i in range(2*n):
    last[cur] = cyc
    nx = nxt[cur]
    if nx<cur+2:
        if cyc==k-1:
            dolast = True
            break
        cyc += 1 + (1 if cur==n-1 and nx==0 else 0)
    cur = nx
    if last[nx]>=0:
        break
#ddprint(f"1 {cyc=} {cur=} last {last[nx]}")

if not dolast:
    # loop: last[cur]*n + cur .. cyc*n + cur
    d = cyc-last[nx]
    cyc += ((k-1-cyc)//d)*d
    #ddprint(f"2 {cyc=} {cur=} {d=} last {last[nx]}")

    # cyc*n + cur
    while cyc<k:
        nx = nxt[cur]
        if nx<cur+2:
            if cyc==k-1:
                break
            cyc += 1 + (1 if cur==n-1 and nx==0 else 0)
        cur = nx
#ddprint(f"3 {cyc=} {cur=}")

# last one mile
last = [-1]*200001
b = [] #[a[cur]]
#last[a[cur]] = cur
if cyc<k:
  for i in range(cur,n):
    j = last[a[i]]
    if j>=0:
        while b[-1]!=a[i]:
            last[b[-1]] = -1
            b.pop()
        last[b[-1]] = -1
        b.pop()
    else:
        b.append(a[i])
        last[a[i]] = i

# output
pad = ''
for x in b:
    printn(pad+str(x))
    pad = ' '
print('')

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint
from copy import deepcopy


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n, k = LI()
A = LI()
D = defaultdict(list)
for i in range(n):
    D[A[i]] += [i]


nxt_idx = [0] * n
for idx_list in D.values():
    for j in range(len(idx_list)):
        nxt_idx[idx_list[j]] = idx_list[(j + 1) % len(idx_list)]



ret = 0
now = 0
L = []
visited = set()
while now not in visited:
    visited.add(now)
    nxt = nxt_idx[now]
    diff = (nxt - now) % n if nxt != now else n
    now = (nxt + 1) % n
    ret += diff + 1
    L += [[ret - 1, nxt]]


ans = []
if (n * k - 1) < ret:
    ss = set()
    for i in range(n * k):
        a = A[i % n]
        if a in ss:
            while a in ss:
                ss.remove(ans.pop())
        else:
            ans += [a]
            ss.add(a)
    print(*ans)
    exit()


ll = (n * k - 1) % ret
bb = bisect_right(L, [ll, INF]) - 1
cc, last_idx = L[bb]
ss = set()
for i in range(ll - cc):
    a = A[(last_idx + i + 1) % n]
    if a in ss:
        while a in ss:
            ss.remove(ans.pop())
    else:
        ans += [a]
        ss.add(a)



print(*ans)

Submission status: Accepted

Solution code:
import collections

n,k=map(int,input().split())
arr=list(map(int,input().split()))
pos=[[] for _ in range(max(arr)+1)]
for i in range(2*n):
  pos[arr[i%n]].append(i)
edge=[[] for _ in range(n)]
cnt=collections.defaultdict(int)
for i in range(n):
  s=pos[arr[i]][cnt[arr[i]]]
  g=pos[arr[i]][cnt[arr[i]]+1]
  edge[s].append((g+1)%n)
  edge[s].append((g+1)//n)
  cnt[arr[i]]+=1
start=0
loop=0
for _ in range(n):
  loop+=edge[start][1]
  start=edge[start][0]
  if start==0:
    break
k%=loop
if k==0:
  print('')
else:
  k-=1
  start=0
  loop=0
  for _ in range(n):
    if loop==k:
      break
    loop+=edge[start][1]
    start=edge[start][0]
  s=set()
  q=collections.deque()
  for i in range(start,n):
    if arr[i] not in s:
      s.add(arr[i])
      q.append(arr[i])
    else:
      while 1:
        tmp=q.pop()
        s.discard(tmp)
        if tmp==arr[i]:
          break
  print(*list(q))

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_right
import sys
input=sys.stdin.readline


def solve():
    N, K = map(int, input().split())
    *A, = map(int, input().split())

    dd = defaultdict(list)
    cc = defaultdict(list)

    for i, j in enumerate(A):
        dd[j].append(i)

    pos, loop = 0, 1
    ans = []

    while pos < N:
        num = A[pos]
        pp = bisect_right(dd[num], pos)
        if pp < len(dd[num]):
            pos = dd[num][pp]+1
        else:
            pos = dd[num][0]+1            
            loop += 1
        cc[loop].append(pos)

    pos = cc[K%loop][0] if cc[K%loop] else 0
    while pos < N:
        num = A[pos]
        pp = bisect_right(dd[num], pos)
        if pp < len(dd[num]):
            pos = dd[num][pp]+1
        else:
            ans.append(num)
            pos += 1
    print(*ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_right

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

dd = defaultdict(list)
cc = defaultdict(list)

for i, j in enumerate(A):
    dd[j].append(i)

pos, loop = 0, 1
ans = []

while pos < N:
    num = A[pos]
    pp = bisect_right(dd[num], pos)
    if pp < len(dd[num]):
        pos = dd[num][pp]+1
    else:
        pos = dd[num][0]+1            
        loop += 1
    cc[loop].append(pos)

pos = cc[K%loop][0] if cc[K%loop] else 0
while pos < N:
    num = A[pos]
    pp = bisect_right(dd[num], pos)
    if pp < len(dd[num]):
        pos = dd[num][pp]+1
    else:
        ans.append(num)
        pos += 1
print(*ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_right

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

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

pos = 0
loop = 1
# l = []
cic = defaultdict(list)

while pos < N:
    num = A[pos]
    
    pp = bisect_right(dd[num], pos)
    if pp < len(dd[num]):
        pos = dd[num][pp]+1
    else:
        pos = dd[num][0]+1            
        loop += 1
    cic[loop].append(pos)

pos = cic[K%loop][0] if cic[K%loop] else 0
ans = []
while pos < N:
    num = A[pos]
    pp = bisect_right(dd[num], pos)
    if pp < len(dd[num]):
        pos = dd[num][pp]+1
    else:
        ans.append(num)
        pos += 1
print(*ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from bisect import bisect_right, bisect_left

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

c = Counter(A)
target = []
d = defaultdict(list)

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

pos = 0
loop = 1
l = []

while pos < N:
    num = A[pos]
    
    pp = bisect_right(dd[num], pos)
    if pp < len(dd[num]):
        pos = dd[num][pp]+1
    else:
        pos = dd[num][0]+1            
        loop += 1
    l.append((num, pos, loop))

for v, pos, p in l:
    if (K-p)%loop==0:
        break

pos = pos if pos<N else 0
ans = []
while pos < N:
    num = A[pos]
    pp = bisect_right(dd[num], pos)
    if pp < len(dd[num]):
        pos = dd[num][pp]+1
    else:
        ans.append(num)
        pos += 1
print(*ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right
from collections import defaultdict

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

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

empty_index = [0]
while True:
    cur_index = empty_index[-1]
    look_for_elem = As[cur_index%N]
    index_of_indices = bisect_right(indices_of_elem[look_for_elem], cur_index%N)
    if len(indices_of_elem[look_for_elem]) ==  index_of_indices:
        pair_end_index = (cur_index // N) * N + indices_of_elem[look_for_elem][0] + N
    else:
        pair_end_index = (cur_index // N) * N + indices_of_elem[look_for_elem][index_of_indices]

    new_index = pair_end_index + 1
    empty_index.append(new_index)
    if new_index % N == 0:
        break
loop = new_index // N

#print(loop, empty_index)

K %= loop

if K == 0:
    exit()
else:
    start = empty_index[bisect_right(empty_index, K * N) - 1] % N
    tmp_ans = As[start:]

#print(tmp_ans)

index_for_tmp_ans = dict()
split = []
for i, elem in enumerate(tmp_ans):
    if elem in index_for_tmp_ans:
        split.append((index_for_tmp_ans[elem], i))
        while True:
            k, v = index_for_tmp_ans.popitem()
            if k == elem:
                break
    else:
        index_for_tmp_ans[elem] = i

for start, end in split:
    tmp_ans[start:end+1] = [-1] * (end - start + 1)

for ans in tmp_ans:
    if ans != -1:
        print(ans, end = ' ')

Submission status: Accepted

Solution code:
N, K, *A = map(int, open(0).read().split())

nxt = [-1] * N
prev = {}
for i, a in enumerate(A + A):
    if a in prev:
        nxt[prev[a]] = i % N
    prev[a] = i % N

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

ans = []
while cur < N:
    if cur >= nxt[cur]:
        ans.append(A[cur])
        cur += 1
    else:
        cur = 1 + nxt[cur]

print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


import bisect

n,k = readints()

a = readints()

place = [[] for i in range(max(a)+1)]

for i,x in enumerate(a):
    place[x].append(i)

now = 0
i = 1
while k>1:
    x = a[now]
    if now >= place[x][-1]:
        i+=1
        k-=1
        now = place[x][0]+1
    else:
        now = place[x][bisect.bisect_right(place[x],now)] + 1
    if now == n:
        now = 0
        k-=1
        k%=i
        if k<1:
            k+=i

ans = []
while now <= n-1:
    x = a[now]
    if now >= place[x][-1]:
        ans.append(x)
        now += 1
    else:
        now = place[x][bisect.bisect_right(place[x],now)] + 1

printline(ans)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    A=LI()
    if N==1:
        if K%2==0:
            ans=[]
            print(' '.join(map(str, ans)))
        else:
            print(A[0])
    else:
        #有向グラフ
        #i番目からスタートした時，次の週のときにどこからスタートしたものと同様になるか，を追えば良い
        #例えば，12323ならば2週目の最初に1が出たときに実質リセットされるので2323をみるのと同じになる
        #これは結局，次に自分と同じ番号が出てくるところの次，なければループ
        M=2*(10**5)
        L=[[]for _ in range(M+1)]#各数字がどこに出てくるか記録
        
        A=A+A+A
        for i in range(N*3):
            L[A[i]].append(i)
            
        nxt=[0]*(N+1)
        
        import bisect
        for i in range(N-1,-1,-1):
            num=bisect.bisect_right(L[A[i]],i)
            nxt_st=L[A[i]][num]
            if nxt_st>=N:
                if nxt_st==2*N-1:
                    nxt[i]=N
                else:
                    nxt[i]=nxt_st+1-N
            else:
                if nxt_st==N-1:
                    nxt[i]=N
                nxt[i]=nxt[(nxt_st+1)%N]
            # print(A[i])
            # print(L[A[i]])
            # print(num)
            # print(nxt_st)
            # print(nxt[i])
            # print("----")
            
        #nxtがわかればあとはダブリング
        N2=50
        dub=[[0]*(N+1) for _ in range(N2)]#最後に注意．1,2,3で3から始めたら次は無
        for i in range(N):#最後はどうせ０なので無視
            dub[0][i]=i
            dub[1][i]=nxt[i]

        
        for j in range(1,N2-1):
            for i in range(N+1):
                dub[j+1][i]=dub[j][dub[j][i]]
                
        # for j in range(10):
        #     print(dub[j])
        
        st=0
        K-=1#このdubやnxtは，次の時にどこから始まるかなので-1
        for j in range(1,N2):#0の時はいらない
            if K&1:
                st=dub[j][st]
            K=K>>1
            
        if st==N:
            ans=[]
            print(' '.join(map(str, ans)))
        else:

            
            ans=[]
            from collections import defaultdict
            dd = defaultdict(int)
            
            for i in range(st,N):
                if dd[A[i]]:
                    x=-1
                    while x!=A[i]:
                        x=ans.pop()
                        dd[x]=0
                else:
                    ans.append(A[i])
                    dd[A[i]]=1
                    
            print(' '.join(map(str, ans)))
        
    
    
    

main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,k = LI()
    a = LI()

    x = collections.defaultdict(int)
    t = [0] * n
    for i in range(n-1,-1,-1):
        t[i] = x[a[i]]
        x[a[i]] = i

    for i in range(n-1,-1,-1):
        t[i] = x[a[i]]
        x[a[i]] = i

    e = n * k
    ei = 0
    i = 0
    while ei < e - n*2:
        j = t[i]
        if j <= i:
            ei += j - i + n + 1
        else:
            ei += j - i + 1
        i = (j + 1) % n
        if i % n == 0:
            ei = e // ei * ei

    r = [0] * n
    ri = 0
    b = {}
    while ei < e:
        c = a[ei%n]
        ei += 1
        if c in b and b[c] < ri and r[b[c]] == c:
            ri = b[c]
            del b[c]
        else:
            r[ri] = c
            b[c] = ri
            ri += 1


    return JA(r[:ri], " ")

print(main())

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    f = {}
    p = {}
    l = [-1] * N
    for i, v in enumerate(A):
        if v not in f:
            f[v] = i
            p[v] = i
        else:
            l[p[v]] = i
            p[v] = i
    t = 0
    r = 0
    while r < K - 1:
        if l[t] == -1:
            r += 1
            t = f[A[t]] + 1
        else:
            t = l[t] + 1
        if t == N:
            r += 1
            r = K - (K % r)
            t = 0
    a = []
    while t < N:
        if l[t] == -1:
            a.append(A[t])
            t += 1
        else:
            t = l[t] + 1
    print(' '.join(str(i) for i in a))
main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

D = defaultdict(list)

for i in range(N):
    D[A[i]].append(i)

next = [None for _ in range(N)]
dist = [None for _ in range(N)]

for v in D.values():
    l = len(v)
    for i in range(l):
        next[v[i]] = (v[(i + 1) % l] + 1) % N
        dist[v[i]] = (v[(i + 1) % l] - v[i] + N - 1) % N + 2

period = 0
node = 0

while node or not period:
    period += dist[node]
    node = next[node]

rem = N * K % period
count = 0
node = 0

while count + dist[node] <= rem:
    count += dist[node]
    node = next[node]

s = []
used = [0 for _ in range(10**6)]

for i in range(rem - count):
    j = (node + i) % N
    if not used[A[j] - 1]:
        used[A[j] - 1] = 1
        s.append(A[j])
    else:
        while True:
            p = s.pop()
            used[p - 1] = 0
            if p == A[j]:
                break

print(*s)

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    I = [0] * N
    T, F = {}, {}
    for i, a in enumerate(A):
        if a not in F:
            F[a] = i
        I[i] = F[a]
        if a in T:
            I[T[a]] = i
        T[a] = i
    t, i = 0, 0
    while i < K - 1:
        if I[t] <= t:
            i += 1
        t = (I[t] + 1) % N
        if t == 0:
            i = K - (K % (i + 1))
    R = []
    while t < N:
        if I[t] <= t:
            R.append(A[t])
            t += 1
        else:
            t = I[t] + 1
    print(' '.join(map(str, R)))

main()

Submission status: Accepted

Solution code:
import bisect

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

ind = [[] for _ in range(2*10**5 + 1)]
for i,num in enumerate(a):
    ind[num].append(i)

for i in range(1,2*10**5 + 1):
    if(ind[i]):
        ind[i].append(ind[i][0] + n)

before = []
cnt = 0
now = a[0]
while(True):
    right = bisect.bisect_right(ind[now], cnt%n)
    cnt += ind[now][right] - ind[now][right-1] + 1
    if(ind[now][right] >= n):
        before.append(ind[now][right-1])
    now = a[cnt%n]
    if(cnt%n == 0):
        break

if(cnt//n==1):
    print('')
    exit()

cyc = k%(cnt//n)

cnt = before[cyc-1]
ans = []
while(cnt < n):
    now = a[cnt]
    right = bisect.bisect_right(ind[now],cnt)
    if(ind[now][right] >= n):
        ans.append(now)
        cnt += 1
    else:
        cnt = ind[now][right] + 1

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

Submission status: Accepted

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

N, K = map(int, input().split())
A = list(map(int, input().split()))
first_idx = {}
for i in range(N)[::-1]:
    first_idx[A[i]] = i
next_idx = {}
dist = [[0] * N for _ in range(41)]
for i in range(N)[::-1]:
    if A[i] in next_idx:
        dist[0][i] = next_idx[A[i]] - i + 1
    else:
        dist[0][i] = N - i + first_idx[A[i]] + 1
    next_idx[A[i]] = i
for j in range(40):
    for i in range(N):
        dist[j+1][i] = dist[j][i] + dist[j][(i + dist[j][i]) % N]
s = []
i = 0
while i < N * K:
    for j in range(41)[::-1]:
        if i + dist[j][i % N] <= N * K:
            i += dist[j][i % N]
            break
    else:
        s.append(A[i % N])
        i += 1
print(*s)

Submission status: Accepted

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

last=[-1]*(2*10**5+1)
nex=[-1]*n
prog=[0]*n

for i,a in enumerate(A*2):
    l=last[a]
    last[a]=i%n
    if nex[l]==-1 and l!=-1:
        nex[l]=(i+1)%n
        if i>=n or i+1==n:
            prog[l]=1
if nex[-1]==0:
    prog[-1]+=1

flag=False #いっぱいループ済か
stage=0
now=0
roop=[-1]*n
while True:
    if roop[now]!=-1 and flag==False:
        flag=True
        rr=stage-roop[now]
        stage=k-1-(k-1-stage)%rr
    if stage+prog[now]>=k:
        break
    roop[now]=stage
    stage+=prog[now]
    now=nex[now]

A=A[now:]+A if k-1-stage else A[now:]
check=[0]*(2*10**5+1)
stack=[]
for a in A:
    if check[a]:
        while check[a]:
            check[stack.pop()]=0
        continue
    stack.append(a)
    check[a]=1

print(*stack)

Submission status: Accepted

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

last=[-1]*(2*10**5+1)
nex=[-1]*n
prog=[0]*n

for i,a in enumerate(A*2):
    l=last[a]
    last[a]=i%n
    if nex[l]==-1 and l!=-1:
        nex[l]=(i+1)%n
        if i>=n or i+1==n:
            prog[l]=1
if nex[-1]==0:
    prog[-1]+=1

flag=False #いっぱいループ済か
stage=0
now=0
roop=[-1]*n
while True:
    if roop[now]!=-1 and flag==False:
        flag=True
        rr=stage-roop[now]
        stage=k-1-(k-1-stage)%rr
    if stage+prog[now]>=k:
        break
    roop[now]=stage
    stage+=prog[now]
    now=nex[now]

A=A[now:]+A if k-1-stage else A[now:]
check=[0]*(2*10**5+1)
stack=[]
for a in A:
    if check[a]:
        while check[a]:
            check[stack.pop()]=0
        continue
    stack.append(a)
    check[a]=1

print(*stack)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N, K = map(int, input().split())
A = list(map(int, input().split()))
log_size = 65
#行き先ではなく移動量をダブリングする
dp = [[-1]*N for _ in range(log_size)]
idx = defaultdict(int)

for i in range(2*N):
    if A[i%N] in idx and idx[A[i%N]]<N:
        dp[0][idx[A[i%N]]] = i+1-idx[A[i%N]]
    
    idx[A[i%N]] = i

for i in range(1, log_size):
    for j in range(N):
        #値が大きくなりすぎるとTLEする
        dp[i][j] = min(10**18, dp[i-1][j]+dp[i-1][(j+dp[i-1][j])%N])

now = 0
NK = N*K

for i in range(log_size-1, -1, -1):
    if NK-dp[i][now]>=0:
        NK -= dp[i][now]
        now = (now+dp[i][now])%N

if NK==0:
    print()
    exit()
    
q = deque([])
cnt = defaultdict(int)

for i in range(now, N):
    if cnt[A[i]]>0:
        while cnt[A[i]]>0:
            rem = q.pop()
            cnt[rem] -= 1
    else:
        cnt[A[i]] += 1
        q.append(A[i])

print(*q)

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:
from collections import defaultdict
from bisect import bisect_right
N,K,*A = map(int, open(0).read().split())
a = A[0]
p = 0
ls = []
dic = defaultdict(list)
for i,c in enumerate(A):
  dic[c].append(i)
while True:
  ls.append(p)
  ind = bisect_right(dic[a],p%N)
  if ind==len(dic[a]):
    ind = 0
    p += N
  p = (p//N)*N+dic[a][ind]+1
  if p%N==0:
    M = p//N
    break
  a = A[p%N]
K %= M
X = N*K
I = bisect_right(ls,X)-1
X -= ls[I]
p = ls[I]%N
S = set()
cnt = 0
ans = []
while X:
  if A[p] not in S:
    S.add(A[p])
    ans.append(A[p])
    cnt += 1
  else:
    i = ans.index(A[p])
    ans = ans[:i]
    S = set(ans)
    cnt = i
  X -= 1
  p += 1
  p %= N
print(' '.join(map(str,ans)))

Submission status: Accepted

Solution code:
from bisect import bisect_right
n, k = map(int, input().split())
a = [int(x) for x in input().split()]

d = {}
for i in range(n):
    if a[i] in d:
        d[a[i]].append(i)
    else:
        d[a[i]] = [i]


def simulate(k):
    if k == 0:
        return 0, []
    lap = 1
    res = [0]
    while True:
        s = res.pop()
        nxt = d[a[s]][bisect_right(d[a[s]], s) % len(d[a[s]])] + 1
        if nxt == n:
            if lap == k and s == n-1:
                res.append(s)
            if s == n-1:
                lap += 1
            return lap, res
        elif nxt <= s+1:
            if lap == k:
                res.append(s)
                if s == n-1:
                    return lap, res
                res.append(s+1)
                if s+1 == n-1:
                    return lap, res
            else:
                res.append(nxt)
                lap += 1
        else:  # s+1 < nxt
            s = nxt
            res.append(s)
    return 0


period, ans = simulate(k)

if period != k:
    lap, ans = simulate(k % period)

print(*[a[x] for x in ans])

Submission status: Accepted

Solution code:
import bisect

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

dic={}
for i in range(N):
    if A[i] not in dic:
        dic[A[i]]=[]
    dic[A[i]].append(i)

check={}
for ai in dic:
    check[ai]=0
    check[ai]=max(dic[ai])


front=[-1]
pos=0
visit=set([-1])
while True:
    val=A[pos]
    if pos>=check[val]:
        front.append(pos)
        if pos in visit:
            break
        else:
            visit.add(pos)
        pos=dic[val][0]+1
        if pos==N:
            front.append(-1)
            break
    else:
        index=bisect.bisect_right(dic[val],pos)
        pos=dic[val][index]+1
        if pos==N:
            front.append(-1)
            break
last=front[-1]
i=front.index(last)
period=len(front)-i-1
const=i
K-=const
K-=1
r=K%period
fff=front[r]
if fff!=-1:
    import heapq
    que=[]
    check={A[i]:0 for i in range(N)}
    index=0
    flag=True
    while N>index:
        if A[index]!=A[fff] and flag:
            index+=1
        elif A[index]==A[fff] and flag:
            index+=1
            flag=False
        else:
            if check[A[index]]==0:
                heapq.heappush(que,(-index,A[index]))
                check[A[index]]=1
                index+=1
            else:
                while True:
                    test,a=heapq.heappop(que)
                    check[a]=0
                    if a==A[index]:
                        break
                check[A[index]]=0
                index+=1
    que.sort(reverse=True)
    que=[que[i][1] for i in range(len(que))]
    print(*que)
else:
    import heapq
    que=[]
    check={A[i]:0 for i in range(N)}
    index=0
    while N>index:
        if check[A[index]]==0:
            heapq.heappush(que,(-index,A[index]))
            check[A[index]]=0
            check[A[index]]=1
            index+=1
        else:
            while True:
                test,a=heapq.heappop(que)
                check[a]=0
                if a==A[index]:
                    break
            check[A[index]]=0
            index+=1
    que.sort(reverse=True)
    que=[que[i][1] for i in range(len(que))]
    print(*que)