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,*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 i<n:
  j=l[i]%len(b[s])
  c+=j<1
  i=b[s][j]+1
  s=a[i%n]
k%=c+1
i=c=0
while i<n:
  j=l[i]%len(b[s])
  if(c>k-2)>j:
    r+=s,
    i+=1
  else:i=b[s][j]+1
  c+=j<1
  s=a[i%n]
print(*r)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import*
from collections import*
n,k,*a=map(int,open(0).read().split())
b=defaultdict(list)
for i,v in enumerate(a):b[v]+=i,
s=a[0]
i=c=0
while 1:
  t=b[s]
  m=len(t)
  j=bisect(t,i)
  c+=j==m
  i=t[j%m]+1
  if i==n:break
  s=a[i]
k%=c+1
s=a[0]
i=c=0
while c<k-1:
  t=b[s]
  m=len(t)
  j=bisect(t,i)
  c+=j==m
  i=t[j%m]+1
  s=a[i]
r=[]
while 1:
  t=b[s]
  m=len(t)
  j=bisect(t,i)
  if j==m:
    r+=s,
    i+=1
  else:
    i=t[j]+1
  if i==n:
    break
  s=a[i]
print(*r)

Submission status: Accepted

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

def getDistNexts(As):
    lenA = len(As)
    poss = dict()
    for i, A in enumerate(As):
        if A not in poss:
            poss[A] = i + lenA

    distNexts = [0]*(lenA)
    for i in reversed(range(lenA)):
        distNexts[i] = poss[As[i]] - i
        poss[As[i]] = i
    return distNexts

distNexts = getDistNexts(As)

NK = N*K

iNow = 0
dist = 0
hists = [-1] * N
hists[0] = 0
isSkipped = False
while dist + distNexts[iNow] + 1 < NK:
    dist += distNexts[iNow] + 1
    iNow = dist % N
    if not isSkipped and hists[iNow] != -1:
        period = dist - hists[iNow]
        dist += (NK-1-dist) // period * period
        isSkipped = True
    hists[iNow] = dist

Ss = []
setS = set()
for _ in range(NK-dist):
    A = As[iNow]
    if A in setS:
        S = ''
        while S != A:
            S = Ss.pop()
            setS.remove(S)
    else:
        Ss.append(A)
        setS.add(A)
    iNow = (iNow+1)%N

if Ss:
    print(' '.join(map(str, Ss)))

Submission status: Accepted

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

def getDistNexts(As):
    lenA = len(As)
    poss = dict()
    for i, A in enumerate(As):
        if A not in poss:
            poss[A] = i + lenA

    distNexts = [0]*(lenA)
    for i in reversed(range(lenA)):
        distNexts[i] = poss[As[i]] - i
        poss[As[i]] = i
    return distNexts

distNexts = getDistNexts(As)

NK = N*K

iNow = 0
dist = 0
hists = [-1] * N
hists[0] = 0
isSkipped = False
while dist + distNexts[iNow] + 1 < NK:
    dist += distNexts[iNow] + 1
    iNow = dist % N
    if not isSkipped and hists[iNow] != -1:
        period = dist - hists[iNow]
        dist += (NK-1-dist) // period * period
        isSkipped = True
    hists[iNow] = dist

Ss = []
setS = set()
for A in As[iNow:]:
    if A in setS:
        S = ''
        while S != A:
            S = Ss.pop()
            setS.remove(S)
    else:
        Ss.append(A)
        setS.add(A)

if Ss:
    print(' '.join(map(str, Ss)))

Submission status: Accepted

Solution code:
def solve():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))

    def getDistNexts(As):
        lenA = len(As)
        poss = dict()
        for i, A in enumerate(As):
            if A not in poss:
                poss[A] = i + lenA

        distNexts = [0]*(lenA)
        for i in reversed(range(lenA)):
            distNexts[i] = poss[As[i]] - i
            poss[As[i]] = i
        return distNexts

    distNexts = getDistNexts(As)

    NK = N*K
    maxD = (NK).bit_length() - 1

    dp = [[0]*(N) for _ in range(maxD+1)]
    for i in range(N):
        dp[0][i] = distNexts[i] + 1
    for d in range(1, maxD+1):
        for i in range(N):
            i2 = i + dp[d-1][i]
            dp[d][i] = i2 + dp[d-1][i2%N] - i

    iNow = 0
    dist = 0
    for d in reversed(range(maxD+1)):
        if dist+dp[d][iNow] < NK:
            dist += dp[d][iNow]
            iNow = dist%N

    Ss = []
    setS = set()
    for A in As[iNow:]:
        if A in setS:
            S = ''
            while S != A:
                S = Ss.pop()
                setS.remove(S)
        else:
            Ss.append(A)
            setS.add(A)

    if Ss:
        print(' '.join(map(str, Ss)))


solve()

Submission status: Accepted

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

from bisect import bisect_left

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

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

L = [N]
ind = N
while True:
    ind = (ind+1)%(N+1)
    if ind == N: break
    a = A[ind]
    if indexes[a][-1] == ind:
        ind = indexes[a][0]
        L.append(ind)
    else:
        loc = bisect_left(indexes[a], ind)
        ind = indexes[a][loc+1]
    

start_ind = L[(K-1)%len(L)] + 1
if start_ind == N+1: start_ind = 0
in_list = {}
for a in A:
    in_list[a] = 0
ans = []
for i in range(start_ind, N):
    a = A[i]
    if in_list[a] == 0:
        ans.append(a)
        in_list[a] = 1
    else:
        while True:
            b = ans.pop()
            in_list[b] -= 1
            if a == b:
                break

for a in ans:
    print(a, end=' ')
print()

Submission status: Accepted

Solution code:
from collections import deque
N, K = map(int, input().split())
A = list(map(int, input().split()))
next_step = [0] * N
memo = [-1] * (2*10**5)
cnt = 0
for i, a in enumerate(A+A):
    if memo[a-1] >= 0:
        if next_step[memo[a-1]%N]:
            continue
        next_step[memo[a-1]%N] = i - memo[a-1] + 1
        if next_step[memo[a-1]%N] == 0:
            pass
        cnt += 1
    if cnt == N:
        break
    memo[a-1] = i

j = 0
while True:
    if j + next_step[j%N] < N*K:
        j += next_step[j%N]
        if j%N == 0:
            j = max(j, N*K//j*j)
    else:
        break

q = deque()
memo = [-1] * (2*10**5)
cnt = 0
for k in range(j, N*K):
    a = A[k%N]
    if memo[a-1] < 0:
        q.append(a)
        memo[a-1] = cnt
        cnt += 1
    else:
        while True:
            b = q.pop()
            memo[b-1] = -1
            if b == a:
                break

print(*q)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    na = [-1 for _ in range(2*n)]
    nk = n * k

    prevai = {}
    for i, _a in enumerate(a+a):
        if _a in prevai:
            na[prevai[_a]] = (i-prevai[_a])%n + 1
            if na[prevai[_a]] == 1:
                na[prevai[_a]] = n+1
        prevai[_a] = i

    doubling = [[0 for _ in range(n)] for _ in range(61)]
    for i in range(n):
        doubling[0][i] = na[i]
    for i in range(1, 61):
        for j in range(n):
            doubling[i][j] = min(doubling[i-1][j] + doubling[i-1][(j+doubling[i-1][j])%n], nk+5)

    tmp = 0
    for i in range(60, -1, -1):
        if nk - tmp >= doubling[i][tmp%n]:
            tmp += doubling[i][tmp%n]

    if tmp == nk:
        return
    
    ans  = []
    adict = {}
    for i in range(tmp%n, n):
        if a[i] in adict and adict[a[i]] > 0:
            while True:
                _a = ans.pop()
                adict[_a] = 0
                if _a == a[i]:
                    break
        else:
            ans.append(a[i])
            adict[a[i]] = 1
    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, K = MAP()
A = LIST()

# 各値毎の出現位置
B = [[] for i in range(max(A)+1)]
for i, a in enumerate(A+A):
    B[a].append(i)
# 同値が何個先で出現するかを保持する
C = [0] * N
for li in B:
    for i in range(len(li)-1):
        if li[i] >= N:
            break
        C[li[i]] = li[i+1] - li[i]

# nxt[k][i] := iからスタートして、2^kブロック移動後の現在位置
nxt = list2d(61, N, 0)
# 初期化
for i in range(N):
    # iからのスタートは、1(2^0)回目はC[i]+1先に進む
    nxt[0][i] = C[i] + 1
# ダブリングのテーブル構築
for k in range(1, 61):
    for i in range(N):
        nxt[k][i] = nxt[k-1][i] + nxt[k-1][(i+nxt[k-1][i])%N]
    if min(nxt[k]) > N*K:
        break

# N*K以内でギリギリまで現在位置を進める
def get_cur():
    i = cur = 0
    while True:
        for k in range(61):
            if cur + nxt[k][i] > N * K:
                if k != 0:
                    cur += nxt[k-1][i]
                    i = cur % N
                    break
                else:
                    return cur
cur = get_cur()

# 最後のブロックについてシミュレーションする
ans = []
s = set()
for i in range(cur, N*K):
    a = A[i%N]
    # 追加
    if a not in s:
        ans.append(a)
        s.add(a)
    # 削除
    else:
        # aが来るまで遡って削除する
        while True:
            key = ans.pop()
            s.remove(key)
            if key == a:
                break
print(*ans)

Submission status: Accepted

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

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

jump_table = [0] * N
for val in temp.values():
    for i in range(len(val)):
        if i == len(val)-1:
            jump_table[val[i]] = val[0]+N-val[i]+1
        else:
            jump_table[val[i]] = val[i+1]-val[i]+1

a = 0
f = 0
while True:
    a += jump_table[a % N]
    if a % N == 0:
        f = a//N
        break

K %= f
a = 0
stack = []
while a < N*K:
    if a + jump_table[a % N] <= N*K:
        a += jump_table[a % N]
    else:
        stack.append(A[a % N])
        a += 1


print(*stack)

Submission status: Accepted

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
a = inl()
nxt = [0]*(2*n)
first = [-1]*n
prev = {}
for i in range(2*n):
    x = a[i%n]
    if x in prev:
        nxt[prev[x]] = i
    prev[x] = i

ddprint(nxt)
#print("hoge")
#exit()  #- no RE.  i.e. RE after here


loopfound = False
i=0
first[0] = 0
while True:
    i0 = i%n
    j = nxt[i0]+1
    nxtj = j + i - i0
    ddprint("  i {} j {} nxtj {} aj0 {}".format(i,j,nxtj,a[j%n]))
    if nxtj >= n*k:
        break
    j0 = j%n
    if first[j0] != -1:
        loopfound = True
        break
    first[j0] = nxtj
    i = nxtj

#print("bar")
#exit()  # still RE.  i.e. RE before here

ddprint(first)
#ddprint("nxtj {} j0 {} lpfd {}".format(nxtj,j0,loopfound))

if loopfound:
    dif = nxtj - first[j0]
    if dif<=0:  # NTBR
        print("foo")
        exit()
    i = nxtj + ((n*k - nxtj) // dif) * dif
    ddprint("nxt {} j0 {} dif {} i {}".format(nxtj,j0,dif,i))
    while True:
        i0 = i%n
        j = nxt[i0] + 1
        nxtj = j+i-i0
        if nxtj >= n*k:
            break
        i = nxtj

ddprint(i)

done = [False] * 200001
stk = []
for j in range(i,n*k):
    ddprint(j)
    ddprint(stk)
    ddprint(done[:11])
    j0 = j%n
    if done[a[j0]]:
        ddprint(a[j0])
        m = len(stk)
        for k in range(m-1,-1,-1):
            x = stk[k]
            ddprint(x)
            stk.pop()
            done[x] = False
            if x==a[j0]:
                break
    else:
        stk.append(a[j0])
        done[a[j0]] = True

for i in stk:
    printn(str(i) + ' ')
print("")

Submission status: Accepted

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

table = {}
init_table = {}
move = {}

for i in range(N):
    if A[i] not in table:
        table[A[i]] = i
        init_table[A[i]] = i
    else:        
        move[table[A[i]]], move[i] = i+1, init_table[A[i]]+1
        table[A[i]] = i

T = K
idx = 0
remain = [0]
for i in range(1, K+1):
    while idx in move and idx < move[idx]:
        idx = move[idx]
    remain.append(idx)
    if(idx == N and i != K):
        T = K % i
        break
    if idx in move:
        idx = move[idx]
    else:
        idx += 1

if(T == 0):
    print()
    exit()
idx = remain[T]
ret = []
while idx < len(A):
    while idx in move and idx < move[idx]:
        idx = move[idx]
    if(idx < len(A)):
        ret.append(A[idx])
    idx += 1

print(*ret)

Submission status: Accepted

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

table = {}
init_table = {}
move = {}

for i in range(N):
    if A[i] in table:
        move[table[A[i]]], move[i] = i+1, init_table[A[i]]+1
    else:
        if A[i] not in init_table:
            init_table[A[i]] = i
    table[A[i]] = i

T = K
idx = 0
remain = [0]
for i in range(1, K+1):
    while idx in move and idx < move[idx]:
        idx = move[idx]
    remain.append(idx)
    if(idx == N and i != K):
        T = K % i
        break
    if idx in move:
        idx = move[idx]
    else:
        idx += 1

if(T == 0):
    print()
    exit()
idx = remain[T]
ret = []
while idx < len(A):
    while idx in move and idx < move[idx]:
        idx = move[idx]
    if(idx >= len(A)):
        break
    ret.append(A[idx])
    idx += 1

print(*ret)

Submission status: Accepted

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

table = {}
init_table = {}
move = {}

for i in range(N):
    if A[i] in table:
        move[table[A[i]]], move[i] = i+1, init_table[A[i]]+1
    else:
        if A[i] not in init_table:
            init_table[A[i]] = i
    table[A[i]] = i

T = K
idx = 0
remain = [0]
for i in range(1, K+1):
    while idx in move and idx < move[idx]:
        idx = move[idx]
    remain.append(idx)
    if(idx == N and i != K):
        T = K % i
        break
    if idx in move:
        idx = move[idx]
    else:
        idx += 1

if(T == 0):
    print()
    exit()
idx = remain[T]
ret = []
while idx < len(A):
    while idx in move and idx < move[idx]:
        idx = move[idx]
    if(idx < len(A)):
        ret.append(A[idx])
    idx += 1

print(*ret)

Submission status: Accepted

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

if n == 1:
    if k % 2:
        print(*arr)
    else:
        print(*[])
    exit()

table = {}
original_table = {}
move = {}

for i, a in enumerate(arr):
    if a not in table:
        table[a] = i
        original_table[a] = i
    else:
        move[table[a]], move[i] = i + 1, original_table[a] + 1
        table[a] = i

res = {}
idx = 0

for i in range(1, k + 1):
    while idx in move and move[idx] > idx:
        idx = move[idx]

    res[i] = idx
    if idx == len(arr):
        k %= len(res)
        if not k:
            k = len(res)
        break

    if idx in move:
        idx = move[idx]
    else:
        idx += 1

idx = res[k]
response = []

while idx < len(arr):
    while idx in move and move[idx] > idx:
        idx = move[idx]
    if idx < len(arr):
        response.append(arr[idx])
    idx += 1

print(*response)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jul 21 23:25:47 2019

@author: Yamazaki Kenichi
"""
import bisect

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

T = [[] for _ in range(2*10**5+1)]

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

s = A[0]
pointa = 0
counta, res = 0, [-1]
while True:
    tmp = bisect.bisect_right(T[s], pointa) % len(T[s])
    p_pointa = pointa
    pointa = T[s][tmp] + 1
    if pointa == p_pointa + 1 or pointa < p_pointa:
        counta += 1
        res.append(p_pointa)
    if pointa == N:
        counta += 1
        res.append(p_pointa)
        break
    s = A[pointa]

ans = []
if K % counta != 0:
    pointa = res[K % counta]
#    ans.append(A[pointa])
    while pointa < N:
        if pointa < T[A[pointa]][-1]:
            tmp = bisect.bisect_right(T[A[pointa]],pointa)
            pointa = T[A[pointa]][tmp] + 1
        else:
            ans.append(A[pointa])
            pointa += 1
#        print(ans)
print(' '.join(map(str,ans)))

Submission status: Accepted

Solution code:
from collections import Counter

n, k = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
OVER_RUN = n*k

cnt = [-1] * (2 * 10**5 + 10)
transition = [[-1] * n for _ in range(58)]
transition[0] = [0 for _ in range(1,n+1)]
for i, item in enumerate(a + a):
    if cnt[item] == -1:
        cnt[item] = i
        continue
    if cnt[item] < n:
        transition[1][cnt[item]] = i+1 - cnt[item]
    cnt[item] = i

for i in range(2,58):
    for j in range(n): 
        walk = transition[i-1][j] + transition[i-1][(transition[i-1][j] + j) % n]
        if walk > OVER_RUN:
            transition[i][j] = OVER_RUN
        else:
            transition[i][j] = walk

step = 0
step_mod = 0
while True:
    itr = 57 
    while transition[itr][step_mod] + step >= OVER_RUN:
        itr -= 1
    step += transition[itr][step_mod]
    step_mod = step % n
    if itr == 0:
        break

# Simulation
target = a[step_mod:]
ans = []
cnt = Counter()
for item in target:
    if cnt[item] > 0:
        while True:
            p = ans.pop()
            cnt[p] -= 1
            if p == item or not p:
                break
    else:
        cnt[item] += 1
        ans.append(item)
print(" ".join([str(item) for item in ans]))

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())
As = list(map(int, input().split()))
M = [[] for i in range(200001)]
for i, a in enumerate(As):
  M[a].append(i)
S = []
for i, a in enumerate(As):
  l = M[a]
  index = l.index(i)
  if index+1 == len(l):
    n = l[0]+N
  else:
    n = l[index+1]
  S.append(n+1-i)
#print(S)
p = 0
while True:
  p = p+S[p%N]
  if p%N == 0:
    break
count = p//N
#print(count)
K = K%count
#print(K)
p = 0
s = []
while p < N*K:
  q = p+S[p%N]
  if q > N*K:
    s.append(As[p%N])
    p = p+1
  else:
    p = q
print(" ".join(map(str, s)))

Submission status: Accepted

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

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

last = dict()
v = [-1] * N

for i, a in enumerate(A + A) :
    if a in last and last[a] < N :
        v[last[a]] = i + 1
    
    last[a] = i

dist = [-1] * N
cur = 0
cycle = 0
while dist[cur] < 0 :
    dist[cur] = cycle 
    cycle += v[cur] - cur
    cur = v[cur] % N

NK = N * K

m = NK % cycle
cur = v[cur] % N
s = 0
while m > dist[cur] > 0 :
    s = dist[cur]
    cur = v[cur] % N
m -= s

ret = []
seen = set()
for a in A[N-m:] :
    if a in seen :
        p = ret.pop()
        seen.remove(a)
        while p != a :
            seen.remove(p)
            p = ret.pop()
    else :
        ret.append(a)
        seen.add(a)
        
print(' '.join([str(i) for i in ret]))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
from collections import defaultdict
d=defaultdict(list)
for i,a in enumerate(A):
    d[a].append(i)
x=0
k=1
from bisect import bisect
while True:
    i=bisect(d[A[x]],x)
    if i==len(d[A[x]]):
        if k==K:
            break
        i=0
        k+=1
    x=d[A[x]][i]+1
    if x==N:
        if K%k==0:
            break
        K=K%k
        k=1
        x=0
t=[]
while x<N:
    i=bisect(d[A[x]],x)
    if i==len(d[A[x]]):
        t.append(A[x])
        x+=1
    else:
        x=d[A[x]][i]+1
print(*t)

Submission status: Accepted

Solution code:
import math

# input
#
# n = 5
# k = 10
# a = [1, 2, 3, 2, 3]

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

# make jumpto
#
# 0 -> 6 (6)
# 1 -> 4 (3)
# 2 -> 5 (3)
# 3 -> 7 (4)
# 4 -> 8 (4)

jumpto = [[-1] * n]
la = -1
li = -1
for (ca, ci) in sorted(zip(a, range(n))):
    if ca == la:
        jumpto[0][ci] = jumpto[0][li] + li - ci
        jumpto[0][li] = ci - li + 1
    else:
        jumpto[0][ci] = n + 1
    la = ca
    li = ci

# doubling jumpto
#
# 0 -> 6 ->  9 (9)
# 1 -> 4 ->  8 (7)
# 2 -> 5 -> 11 (9)
# 3 -> 7 -> 10 (7)
# 4 -> 8 -> 12 (8)
#
# 0 -> 6 ->  9 -> 13 -> 17 (17)
# 1 -> 4 ->  8 -> 12 -> 15 (14)
# 2 -> 5 -> 11 -> 14 -> 18 (16)
# 3 -> 7 -> 10 -> 16 -> 19 (16)
# 4 -> 8 -> 12 -> 15 -> 21 (17)

levels = int(math.log(k, 2))
for l in range(1, levels + 1):
    jumpto.append([-1] * n)
    for i in range(n):
        f = jumpto[l - 1][i]
        s = jumpto[l - 1][(i + f) % n]
        jumpto[l][i] = f + s

# step1 and step2
ret = []
s = 0
while s < n * k:
    jumped = False
    for l in range(levels, -1, -1):
        if s + jumpto[l][s % n] <= n * k:
            s += jumpto[l][s % n]
            jumped = True
            break
    if not jumped:
        ret.append(str(a[s % n]))
        s += 1

print(' '.join(ret))

Submission status: Accepted

Solution code:
import math

# input
#
# n = 5
# k = 10
# a = [1, 2, 3, 2, 3]

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

# make jumpto
#
# 0 -> 6 (5)
# 1 -> 4 (2)
# 2 -> 5 (2)
# 3 -> 7 (3)
# 4 -> 8 (3)

jumpto = [[-1] * n]
la = -1
li = -1
for (ca, ci) in sorted(zip(a, range(n))):
    if ca == la:
        jumpto[0][ci] = jumpto[0][li] + li - ci
        jumpto[0][li] = ci - li
    else:
        jumpto[0][ci] = n
    la = ca
    li = ci

# doubling jumpto
#
# 0 -> 6 ->  9 (8)
# 1 -> 4 ->  8 (6)
# 2 -> 5 -> 11 (8)
# 3 -> 7 -> 10 (6)
# 4 -> 8 -> 12 (7)
#
# 0 -> 6 ->  9 -> 13 -> 17  (16)
# 1 -> 4 ->  8 -> 12 -> 15  (13)
# 2 -> 5 -> 11 -> 14 -> 18  (15)
# 3 -> 7 -> 10 -> 16 -> 19  (15)
# 4 -> 8 -> 12 -> 15 -> 21  (16)

levels = int(math.log(k, 2))
for l in range(1, levels + 1):
    jumpto.append([-1] * n)
    for i in range(n):
        f = jumpto[l - 1][i]
        s = jumpto[l - 1][(i + f + 1) % n]
        jumpto[l][i] = f + 1 + s

# step1
s = 0
while True:
    jumped = False
    for l in range(levels, -1, -1):
        if s + jumpto[l][s % n] < n * k:
            s += jumpto[l][s % n] + 1
            jumped = True
            break
    if not jumped:
        break

# step2
ret = []
while s < n * k:
    if s + jumpto[0][s % n] < n * k:
        s = s + jumpto[0][s % n] + 1
    else:
        ret.append(str(a[s % n]))
        s += 1

print(' '.join(ret))

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]

    n_head_pos = dict() #一番最初にnが出てくるindex
    rem_head_num = [-1] * N #i番目から処理を始めた時に残る数列の先頭の数字
    for i in reversed(range(N)):
        if A[i] not in n_head_pos:
            rem_head_num[i] = A[i]
        else:
            if n_head_pos[A[i]] == N-1: rem_head_num[i] = -1
            else: rem_head_num[i] = rem_head_num[n_head_pos[A[i]] + 1]
        n_head_pos[A[i]] = i
    #print(n_head_pos)
    #print(rem_head_num)

    start_cycle = [] #先頭の数字の周期
    start = -1
    used = set()
    while start not in used:
        used |= {start}
        start_cycle.append(start)
        if start == -1: next = rem_head_num[0]
        elif n_head_pos[start] < N - 1: next = rem_head_num[n_head_pos[start] + 1]
        else: next = -1
        start = next

    #print(start_cycle)

    len_cycle = len(start_cycle)
    last = (K - 1) % len_cycle 
    #print(last)
    if start_cycle[last] == -1: start_index = 0
    elif n_head_pos[start_cycle[last]] < N - 1: start_index =n_head_pos[start_cycle[last]] + 1
    else: start_index == -1
    #print(start_index)
    if start_index >= 0:
        out = []
        using = dict()
        l = 0
        for i in range(start_index, N):
            if A[i] in using:
                aindex = using[A[i]]
                l = aindex
                for a in out[aindex:]:
                    using.pop(a)
                out = out[:aindex]
            else:
                out.append(A[i])
                using[A[i]] = l
                l += 1
                #print(out, using, l)
        print(" ".join(map(str, out)))
    else: print(" ")

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import bisect
import sys
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(index):
  if index == N:
    ans.append(-1)
    return
  num = a[index]
  if len(data[num]) == 1:
    ans.append(index)
    tami(index+1)
  elif index == data[num][-1]:
    ans.append(index)
    tami(data[num][0]+1)
  else:
    tmp = bisect.bisect_left(data[num],index)
    #print(num,data[num],tmp)
    tami(data[num][tmp+1]+1)

N,K = IL()
a = IL()

data = [[] for i in range(200010)]
ans = []

for i in range(N):
  data[a[i]].append(i)

#print(data)

tami(0)

#print(ans)
#print(len(ans),K)
#print(K%len(ans))

if K%len(ans) == 0:
  print()
else:
  x = ans[K%len(ans)-1]
  d = []
  d.append(a[x])
  while x != N-1:
    x += 1
    if len(data[a[x]]) == 1:
      d.append(a[x])
    elif x == data[a[x]][-1]:
      d.append(a[x])
    else:
      tmp = bisect.bisect_left(data[a[x]],x)
      x = data[a[x]][tmp+1]

  print(" ".join(map(str,d)))

"""
for i in range(K):
  for j in range(N):
    if a[j] in data:
      num = data.index(a[j])
      data = data[:num]
    else:
      data.append(a[j])
  print(data)

11 10
1 2 3 0 4 5 6 0 4 5 6

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

10 10
1 4 8 3 5 4 2 3 4 6
"""