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: Wrong Answer

Solution code:
from collections import deque


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

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

memo = {}
next_ = [-1] * n
for i in range(n)[::-1]:
    memo[a[i]] = i + n
for i in range(n)[::-1]:
    next_[i] = memo[a[i]] + 1
    memo[a[i]] = i

for i in range(n)[::-1]:
    if next_[i] >= n - 1:
        doubling[0][i] = next_[i]
    else:
        doubling[0][i] = next_[next_[i]]
        next_[i] = next_[next_[i]]

for i in range(n)[::-1]:          
    doubling[0][i] = doubling[0][i] % n
for t in range(1, log_size):
    for i in range(n):
        doubling[t][i] = doubling[t-1][doubling[t-1][i] % n]

pos = 0
cnt = 0
k -= 1
while k != 0:
    pos %= n
    if k % 2 == 1:
        pos = doubling[cnt][pos]
    k = k // 2
    cnt += 1
start = pos % n

memo_set = set([])
q = deque([])
if start == n-1:
    print()
    exit()
for i in range(start, n):
    if a[i] not in memo_set:
        q.append(a[i])
        memo_set.add(a[i])
    else:
        while True:
            k = q.pop()
            memo_set.remove(k)
            if k == a[i]:
                break
print(*q)

Submission status: Wrong Answer

Solution code:
from collections import deque


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

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

memo = {}
next_ = [-1] * n
for i in range(n)[::-1]:
    memo[a[i]] = i + n
for i in range(n)[::-1]:
    next_[i] = memo[a[i]] + 1
    memo[a[i]] = i

for i in range(n)[::-1]:
    if next_[i] >= n:
        doubling[0][i] = next_[i]
    else:
        doubling[0][i] = next_[next_[i]]
        next_[i] = next_[next_[i]]

for i in range(n)[::-1]:          
    doubling[0][i] = doubling[0][i] % n
for t in range(1, log_size):
    for i in range(n):
        doubling[t][i] = doubling[t-1][doubling[t-1][i] % n]

pos = 0
cnt = 0
k -= 1
while k != 0:
    pos %= n
    if k % 2 == 1:
        pos = doubling[cnt][pos]
    k = k // 2
    cnt += 1
start = pos % n

memo_set = set([])
q = deque([])
for i in range(start, n):
    if a[i] not in memo_set:
        q.append(a[i])
        memo_set.add(a[i])
    else:
        while True:
            k = q.pop()
            memo_set.remove(k)
            if k == a[i]:
                break
print(*q)

Submission status: Wrong Answer

Solution code:
mi = lambda: map(int, input().split())
e = enumerate
n,k = mi()
a = list(mi())
g = [None]*n

d = dict()
for i,x in e(a):
  d[x] = i
for i,x in e(a):
  g[d[x]] = ((i+1)%n,int(d[x]>=i)+int(i+1==n))
  d[x] = i
db = [g]
for _ in range(100):
  old = db[-1]
  new = [None]*n
  for i in range(n):
    p,q = old[i]
    r,s = old[p]
    new[i] = (r,q+s)
  db.append(new)
print(0)
exit()
cur = 0
st = 100
cs = 0
while st>=0:
  p,q = db[st][cur]
  if cs+q < k:
    cs += q
    cur = p
  else:
    st -= 1
q = list()
for x in a[cur:]:
  if x in q:
    t = x-1
    while t != x:
      t = q.pop()
  else:
    q.append(x)
print(' '.join(map(str,q)))

Submission status: Wrong Answer

Solution code:
mi = lambda: map(int, input().split())
e = enumerate
n,k = mi()
a = list(mi())
g = [None]*n

d = dict()
for i,x in e(a):
  d[x] = i
for i,x in e(a):
  g[d[x]] = ((i+1)%n,int(d[x]>=i)+int(i+1==n))
  d[x] = i
db = [g]
for _ in range(100):
  old = db[-1]
  new = [None]*n
  for i in range(n):
    p,q = old[i]
    r,s = old[p]
    new[i] = (r,q+s)
  db.append(new)
cur = 0
st = 100
cs = 0
while st>=0:
  p,q = db[st][cur]
  if cs+q < k:
    cs += q
    cur = p
    print(cs)
  else:
    st -= 1
q = list()
for x in a[cur:]:
  if x in q:
    t = x-1
    while t != x:
      t = q.pop()
  else:
    q.append(x)
print(' '.join(map(str,q)))

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

L = [-1]*N
used = [-1]*(2*10**5+1)
used1 = [-1]*(2*10**5+1)
for i in range(N-1, -1, -1):
    if used1[A[i]] == -1:
        used[A[i]] = i
        used1[A[i]] = i
    else:
        L[i] = used[A[i]]-i
        used[A[i]] = i
        
for i in range(N):
    if L[i] == -1:
        if used1[A[i]] == used[A[i]]:
            L[i] = N
        else:
            L[i] = N-used1[A[i]]+used[A[i]]

T = 1
idx = 0
while T%N != 1 or T < N:
    T += L[idx]+1
    idx += L[idx]+1
    idx %= N

T -= 1
K = (N*K) % T
idx = 0
while K-L[idx]-1 > 0:
    K -= L[idx]+1
    idx += L[idx]+1
    idx %= N
    
ans = []
while K:
    if L[idx] < K:
        K -= L[idx]+1
        idx -= L[idx]+1
        idx %= N
    else:
        ans.append(str(A[idx]))
        idx += 1
        idx %= N
        K -= 1
        
print(" ".join(ans))

Submission status: Wrong Answer

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 i<k-2:
  t=b[s]
  m=len(t)
  j=bisect(t,i)
  c+=j==m
  i=t[j%m]+1
  s=a[i]
s=[]
for i in a[i:]+a:
  if i in s:s=s[:s.index(i)]
  else:s+=i,
print(*s)

Submission status: Wrong Answer

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=[]
for i in a*k:
  if i in s:s=s[:s.index(i)]
  else:s+=i,
print(*s)
"""

Submission status: Wrong Answer

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)]
in_list = {}
for a in A:
    in_list[a] = 0
ans = []
for i in range(start_ind+1, 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: Wrong Answer

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 = [0]
ind = 0
while True:
    a = A[ind]
    if indexes[a][-1] == ind:
        ind = (indexes[a][0]+1)%N
        if ind == 0: break
        L.append(ind)
    else:
        loc = bisect_left(indexes[a], ind)
        ind = (indexes[a][loc+1]+1)%N
        if ind == 0: break
    

start_ind = L[(K-1)%len(L)]
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: Wrong Answer

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]

# 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 = []
d = {}
# 開始位置によって切り出し位置を調整
offset = cur
for i in range(cur, N*K):
    a = A[i%N]
    # 追加
    if a not in d:
        ans.append(a)
        d[a] = i
    # 削除
    else:
        s = set(ans[d[a]-offset:])
        ans = ans[:d[a]-offset]
        # 次回切り出し位置用に調整
        offset += 2
        # 今回切り出して消した分をdictからも削除
        for key in s:
            d.pop(key)
            offset += 1
print(*ans)

Submission status: Wrong Answer

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]

# 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 = []
d = {}
# 開始位置によって切り出し位置を調整
offset = cur
for i in range(cur, N*K):
    a = A[i%N]
    # 追加
    if a not in d:
        ans.append(a)
        d[a] = i
    # 削除
    else:
        s = set(ans[d[a]-offset:])
        ans = ans[:d[a]-offset]
        # 次回切り出し位置用に調整
        offset += 1
        # 今回切り出して消した分をdictからも削除
        for key in s:
            d.pop(key)
            offset += 1
print(*ans)

Submission status: Wrong Answer

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]

# 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 = []
d = {}
# 開始位置によって切り出し位置を調整
offset = cur % N
for i in range(cur, N*K):
    i %= N
    a = A[i]
    # 追加
    if a not in d:
        ans.append(a)
        d[a] = i
    # 削除
    else:
        s = set(ans[d[a]-offset:])
        ans = ans[:d[a]-offset]
        # 次回切り出し位置用に調整
        offset += 1
        # 今回切り出して消した分をdictからも削除
        for key in s:
            d.pop(key)
            offset += 1
print(*ans)

Submission status: Wrong Answer

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]

# 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 = []
d = {}
# 開始位置によって切り出し位置を調整
offset = cur % N
for i in range(cur, N*K):
    i %= N
    a = A[i]
    # 追加
    if a not in d:
        ans.append(a)
        d[a] = i
    # 削除
    else:
        s = set(ans[d[a]-offset:])
        ans = ans[:d[a]-offset]
        # 今回切り出して消した分をdictからも削除
        for key in s:
            d.pop(key)
            # 次回切り出し位置用に調整
            offset += 2
print(*ans)