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:
from sys import exit, setrecursionlimit, stdin, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *
from heapq import *
import operator
import math
from fractions import gcd
from random import randint

setrecursionlimit(10**8)

def input():
  return stdin.readline().strip()

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N, K = reads()
A = reads()

skip = [-1] * (N + 1)
first_occ = {}
for i in range(N-1, -1, -1):
  a = A[i]
  if a in first_occ:
    if first_occ[a] < N-1:
      skip[i] = skip[first_occ[a] + 1]
    else:
      skip[i] = first_occ[a] + 1
  else:
    skip[i] = i
  first_occ[a] = i
skip[N] = N

back = [first_occ[A[i]] + 1 for i in range(N)] + [0]
next_state = [skip[back[q]] for q in range(N+1)]


q = skip[0]

rev = {}
memo = {}
i = 0
while True:
  if q in rev:
    j = rev[q]
    break
  rev[q] = i
  memo[i] = q
  q = next_state[q]
  i += 1

m = i - j
q = memo[j + (K - 1 - j) % m]

s = []
while q < N:
  if skip[q] == q:
    s.append(A[q])
    q += 1
  else:
    q = skip[q]

print(*s)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

MAX = 10**5*2+3

N,K = inpl()
aa = inpl()
cnts = defaultdict(int)
inds = defaultdict(list)
info = [[0,0] for _ in range(N)]
ed = set(aa)

for i,a in enumerate(aa):
    cnts[a] += 1
    inds[a].append(i)     # inds[a][i-1] : a の i番目の index
    info[i] = [a,cnts[a]] # aa[i] -> info[i][1] 番目の info[i][0]


nexts = [-1]*MAX
ed.add(0)
for e in ed:
    tmp = e
    if e == 0:
        i = 0
    else:
        i = inds[tmp][0] + 1

    while True:
        #print(tmp,i)
        if i == N:
            nexts[e] = 0
            break
        tmp,n = info[i]
        if cnts[tmp] == n:
            nexts[e] = tmp
            break
        else: #cnts[a] != n
            nextind = inds[tmp][n+1-1] # tmpの値の次のindex
            nextind += 1 # の一個次
            i = nextind


visited = [False]*MAX
kero = []
x = 0
L = 0
while True:
    if visited[x]:
        break
    else:
        kero.append(x)
        visited[x] = True
        x = nexts[x]
        L += 1

tmp = kero[K%L-1]
#print(kero)
#print(tmp)

ans = []
if tmp == 0:
    i = 0
else:
    i = inds[tmp][0] + 1

while i < N:
    tmp,n = info[i]
    if cnts[tmp] == n:
        ans.append(tmp)
        i += 1
    else:
        nextind = inds[tmp][n+1-1] # tmpの値の次のindex
        nextind += 1 # の一個次
        i = nextind

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from collections import defaultdict

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

AA = A + A # 2周分
next_same = [None] * (2*N)
last_pos = defaultdict(lambda: None)

for i,a in enumerate(AA):
    j = last_pos[a]
    if j is None:
        last_pos[a] = i
    else:
        next_same[j] = i
        last_pos[a] = i

# Xの添字で、最後にvisitしたときを持つ。visit = （そこからスタート！）

NK = N * K
visited = [None] * N
x = 0
visited[0] = 0
while True:
    y = next_same[x % N] + (x//N) * N + 1
    if y >= NK:
        break
    if visited[y % N] is not None:
        # 周期が見つかった！
        P = y - visited[y % N]
        y += (NK - y) // P * P
        x = y
        break
    else:
        visited[y % N] = y
        x = y

answer = []
while x < NK:
    y = next_same[x % N] + (x//N) * N + 1
    if y > NK:
        answer.append(A[x%N])
        x += 1
        continue
    x = y

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

Submission status: Accepted

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

C = Counter()
table = [None]*N
for i in range(N-1, -1, -1):
    a = A[i]
    C[a] = i
for i in range(N-1, -1, -1):
    a = A[i]
    table[i] = C[a]
    C[a] = i
cost = [1 + table[i] - i if table[i] > i else 1+ table[i] - i + N for i in range(N)] 
table = [(1+t)%N for t in table]
loop = 0
st = 0
en = None
while en != 0:
    en = table[st]
    loop += cost[st]
    st = en
K = (N*K) % loop
st = 0
while K - cost[st] >= 0:
    K -= cost[st]
    st = table[st]
sS = set()
S = []
for i in range(K):
    a = A[(st+i)%N]
    if a in sS:
        sS.remove(a)
        while S[-1] != a:
            sS.remove(S.pop())
        S.pop()
    else:
        S.append(a)
        sS.add(a)
print(*S)

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))

# 次 A[j] が取り除かれるまでの操作回数
counts = [0] * N
D = {}
for i, a in enumerate(A + A):
    if a not in D:
        D[a] = i
    else:
        if D[a] < N:
            counts[D[a]] = i - D[a]
            D[a] = i

circle = counts[0] + 1
i = (counts[0] + 1) % N
while i != 0:
    circle += counts[i] + 1
    i = (i + counts[i] + 1) % N
rem = N * K % circle

ans = []

i = 0
while rem > 0:
    while rem - counts[i] > 0:
        rem -= counts[i] + 1
        i = (i + counts[i] + 1) % N
    if rem:
        ans.append(A[i])
        rem -= 1
        i = (i + 1) % N

if ans:
    print(*ans)

# hist = []
# stack = []
# for _ in range(K):
#     for a in A:
#         if a in stack:
#             while a in stack:
#                 stack.pop()
#         else:
#             stack.append(a)
#
#         hist.append(a)
#         print(hist)
#         print('', stack)
#         print()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [int(a) for a in input().split()]
M = 200100
P = [-1 for i in range(M)]
NE = [-1 for a in range(N)]
for i in range(N):
    if P[A[i]] >= 0 and NE[P[A[i]]] < 0:
        NE[P[A[i]]] = i
    P[A[i]] = i
for i in range(N):
    if P[A[i]] >= 0 and NE[P[A[i]]] < 0:
        NE[P[A[i]]] = i
    P[A[i]] = i

i = 0
c = 1
while True:
    if NE[i] <= i: c += 1
    i = (NE[i] + 1) % N
    if i == 0:
        break
K %= c
ANS = []
i = 0
while K:
    while NE[i] > i:
        i = (NE[i] + 1) % N
    if K >= 2:
        i = (NE[i] + 1) % N
        K -= 1
    else:
        break
while i < N:
    if NE[i] > i:
        i = NE[i] + 1
    else:
        ANS.append(A[i])
        i += 1
print(*ANS)

Submission status: Runtime Error

Solution code:
import bisect
N, K, *A = [int(_) for _ in open(0).read().split()]
K -= 1
L = [[] for _ in range(10)]
for i, a in enumerate(A * 2):
    L[a] += [i]
exit()
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:
        raise
else:
    B = A
ans = []
cnt = [0] * 10
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: Runtime Error

Solution code:
import bisect
N, K, *A = [int(_) for _ in open(0).read().split()]
K -= 1
L = [[] for _ in range(10)]
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
exit()
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:
        raise
else:
    B = A
ans = []
cnt = [0] * 10
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: Runtime Error

Solution code:
import bisect
N, K, *A = [int(_) for _ in open(0).read().split()]
K -= 1
L = [[] for _ in range(10)]
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)
exit()
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:
        raise
else:
    B = A
ans = []
cnt = [0] * 10
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: Runtime Error

Solution code:
import bisect
N, K, *A = [int(_) for _ in open(0).read().split()]
K -= 1
L = [[] for _ in range(10)]
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:
        raise
else:
    B = A
ans = []
cnt = [0] * 10
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: Runtime Error

Solution code:
import bisect
N, K, *A = [int(_) for _ in open(0).read().split()]
K -= 1
L = [[] for _ in range(10)]
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)
for i in range(N - 1, -1, -1):
    if first_cycle[i] == K2:
        break
ans = []
cnt = [0] * 10
for a in A[i:]:
    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: Runtime Error

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
    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
        cur = nx
#ddprint(f"3 {cyc=} {cur=}")

# last one mile
last = [-1]*200001
b = [a[cur]]
last[a[cur]] = cur
for i in range(cur+1,n):
    j = last[a[i]]
    if j>=0:
        for m in range(i-1,j-1,-1):
            last[a[m]] = -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: Runtime Error

Solution code:
１

Submission status: Runtime Error

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
    # l.append((pos, loop))
    cic[loop].append(pos)

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

if cic[K%loop]:
    print()
else:
    pos = cic[K%loop][0] #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: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
As = list(input().split())

SET = set()
ans = []
for i in range(1, K+1):
    lis = []
    s = set()
    for j in range(i):
        for a in As:
            if a in s:
                lis = lis[:lis.index(a)]
                s = set(lis)
            else:
                s.add(a)
                lis.append(a)
    string = ' '.join(lis)
    if string in SET:
        break
    SET.add(string)
    ans.append(string)

print(ans[K%(i-1)-1])

Submission status: Runtime Error

Solution code:
a,b=map(int,input().split())
L=list(map(int,input().split()))
L=L*b
R=list()
for i in range(a*b):
  if L[i] not in R:
    R.append(L[i])
  else:
    a=R.index(L[i])
    del R[a:]
print(" ".join(map(str,R)))

Submission status: Runtime Error

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(max(A))]

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:
        used[A[j] - 1] = 0
        while True:
            p = s.pop()
            if p == A[j]:
                break

print(*s)

Submission status: Runtime Error

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(N)]

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:
        used[A[j] - 1] = 0
        while True:
            p = s.pop()
            if p == A[j]:
                break

print(*s)

Submission status: Runtime Error

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

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)))
print(before)

Submission status: Runtime Error

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]
    cnt = i
  X -= 1
  p += 1
  p %= N
print(' '.join(map(str,ans)))

Submission status: Runtime Error

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

remain = [''] * (N+1) # 一番後ろは番兵
d = {}
for i, a in enumerate(A[::-1]):
  j = N - 1 - i
  if a in d:
    idx = d[a][-1]
    remain[j] = remain[idx+1]
    d[a].append(j)
  else:
    remain[j] = str(a) + ' ' + remain[j+1]
    d[a] = [j]

cands = []
idx = 0
for k in range(1, K+1):
  S = remain[idx]
  cands.append(S)
  if S == '':
    break
  s = int(S.split()[0])
  idx = d[s][-1] + 1

K = K % k
print(cands[K-1])

Submission status: Runtime Error

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

remain = [''] * (N+1) # 一番後ろは番兵
d = {}
for i, a in enumerate(A[::-1]):
  j = N - 1 - i
  if a in d:
    idx = d[a][-1]
    remain[j] = remain[idx+1]
    d[a].append(j)
  else:
    remain[j] = str(a) + remain[j+1]
    d[a] = [j]

cands = []
idx = 0
for k in range(1, K+1):
  S = remain[idx]
  cands.append(S)
  if S == '':
    break
  s = int(S[0])
  idx = d[s][-1] + 1

K = K % k
print(' '.join(cands[K-1]))

Submission status: Runtime Error

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 < N*(K-1):
        if last_step[now]!=-1:
            step_size = accumulate_step - last_step[now]
            break
        last_step[now] = accumulate_step
        before = now 
        now = next_[before] + 1
        accumulate_step += now - before 
        now %= N

    seq = []
    remain = -1
    if step_size == 0:#愚直に試す
        remain = N*K - accumulate_step 
    else:
        raise Exception
        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))
    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
    # ans2 = []
    # cnt2 = defaultdict(int)
    # for a in A[:N]*K:
    #     if not cnt2[a]:
    #         cnt2[a] += 1
    #         ans2.append(a)
    #         continue
    #     while cnt2[a]:
    #         cnt2[ans2.pop()]-=1
    # print(ans2)

    print(*ans)


    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

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 < N*(K-1):
        if last_step[now]!=-1:
            step_size = accumulate_step - last_step[now]
            break
        last_step[now] = accumulate_step
        before = now 
        now = next_[before] + 1
        accumulate_step += now - before 
        # print(before,now,accumulate_step)
        now %= N

    seq = []
    remain = -1
    if step_size == 0:#愚直に試す
        remain = N*K - accumulate_step 
    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))
    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
    # ans2 = []
    # cnt2 = defaultdict(int)
    # for a in A[:N]*K:
    #     if not cnt2[a]:
    #         cnt2[a] += 1
    #         ans2.append(a)
    #         continue
    #     while cnt2[a]:
    #         cnt2[ans2.pop()]-=1
    # print(ans2)

    print(*ans)


    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
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]] = i
                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):
                    ans.pop()
                cou = sr-1
            cou += 1
    print(" ".join(ans))

Submission status: Runtime Error

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]]]
      cnt = ind[A[c]]-1
  print(*ans)

Submission status: Runtime Error

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:
    print()
else:
    ans = []
    anss = set()
    for a in A[j%N:]:
        if a in anss:
            anss.remove(a)
            while ans[-1] != a:
                ans.pop()
            ans.pop()
        else:
            anss.add(a)
            ans.append(a)
    print(*ans)