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:
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:
            print()
        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
        
        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:
                nxt[i]=(nxt_st+1)%N
            else:
                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=[[-1]*N for _ in range(N2)]
        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):
                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

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

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()
    #有向グラフ
    #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
    
    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:
            nxt[i]=(nxt_st+1)%N
        else:
            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=[[-1]*N for _ in range(N2)]
    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):
            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

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

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()
    #有向グラフ
    #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
    
    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:
            nxt[i]=(nxt_st+1)%N
        else:
            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=45
    dub=[[-1]*N for _ in range(N2)]
    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):
            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

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

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()
    #有向グラフ
    #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
    
    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:
            nxt[i]=(nxt_st+1)%N
        else:
            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=34
    dub=[[-1]*N for _ in range(N2)]
    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):
            dub[j+1][i]=dub[j][dub[j][i]]
     
    st=0
    K-=1#このdubやnxtは，次の時にどこから始まるかなので-1
    for j in range(1,N2):#0の時はいらない
        if K&1:
            st=dub[j][st]
        K=K>>1

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

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:
        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:
            ri = b[c]
            del b[c]
        else:
            r[ri] = c
            b[c] = ri
            ri += 1


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

print(main())

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = [int(x)-1 for x in input().split()]

inds = [[] for _ in range(max(a)+1)]
y = [0]*n

for i in range(n):
    if inds[a[i]]:
        y[inds[a[i]][-1]] = i+1 - inds[a[i]][-1]
    inds[a[i]].append(i)

for j in range(max(a)+1):
    if inds[j]:
        y[inds[j][-1]] = n+inds[j][0]+1 - inds[j][-1]

length = (n*k).bit_length()

db = [y]
for m in range(length):
    next_y = [0]*n
    for i in range(n):
        next_y[i] = db[-1][i] + db[-1][(i+db[-1][i]) % n]
    db.append(next_y)

cur = 0
i = length

while cur < n*k:
    while i > -1 and cur + db[i][cur % n] > n*k:
        i -= 1
    if i == -1:
        break
    cur = cur + db[i][cur % n]

ans = []
while cur < n*k:
    if cur + db[0][cur % n] > n*k:
        ans.append(cur)
        cur += 1
    elif cur + db[0][cur % n] == n*k:
        break
    else:
        cur = cur + db[0][cur % n]
        ans.append(cur)

print(*map(lambda x: a[x % n]+1, ans))

Submission status: Wrong Answer

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
        if dist[v[i]] == 1:
            dist[v[i]] += N

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 = []
R = defaultdict(lambda: -1)

for i in range(rem - count):
    j = (node + i) % N
    if R[A[j]] == -1:
        R[A[j]] = i
        s.append(A[j])
    else:
        s = s[:R[A[j]]]
        R[A[j]] = -1

print(*s)

Submission status: Wrong Answer

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 = []
R = defaultdict(lambda: -1)

for i in range(rem - count):
    j = (node + i) % N
    if R[A[j]] == -1:
        R[A[j]] = i
        s.append(A[(node + i) % N])
    else:
        s = s[:R[A[j]]]
        R[A[j]] = -1

print(*s)

Submission status: Wrong Answer

Solution code:
import bisect
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    if len(A) == len(set(A)):
        print(' '.join(str(i) for i in A[(K % N)-1:]))
        return
    d = {}
    for i, v in enumerate(A):
        if v in d:
            d[v].append(i)
        else:
            d[v] = [i]
    t = 0
    l = []
    count = 0
    while count < 10:
        count += 1
        if len(d[A[t]]) == 1:
            if t == N-1:
                break
            t += 1
        else:
            x = bisect.bisect_right(d[A[t]], t)
            if x == len(d[A[t]]):
                t = d[A[t]][0] + 1
            else:
                if d[A[t]][x] == N - 1:
                    break
                t = d[A[t]][x] + 1
        l.append(t)
    n = K % len(l) - 1
    r = []
    t = l[n]
    while t < N-1:
        if len(d[A[t]]) == 1:
            r.append(A[t])
            t += 1
        else:
            x = bisect.bisect_right(d[A[t]], t)
            if x == len(d[A[t]]):
                r.append(A[t])
            elif d[A[t]][x] == N - 1:
                break
            else:
                t = d[A[t]][x] + 1
    print(' '.join(str(i) for i in r))
main()

Submission status: Wrong Answer

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

last=[-1]*(2*10**5+1)
num=[0]*(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

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]

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

print(*stack)

Submission status: Wrong Answer

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]
S = set()
p = ls[I]%N
D = defaultdict(list)
cnt = 0
ans = []
while X:
  if D[A[p]]==[]:
    D[A[p]].append(cnt)
    ans.append(A[p])
    cnt += 1
  else:
    i = D[A[p]][0]
    ans = ans[:i]
    cnt = i
  X -= 1
  p += 1
  p %= N
print(' '.join(map(str,ans)))

Submission status: Wrong Answer

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

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

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


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

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

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

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

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

print(*ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect
from collections import defaultdict
n, k = map(int, input().split())
*a, = map(int, input().split())
idx = defaultdict(list)
for i, x in enumerate(a):
	idx[x].append(i)
m = (k * n).bit_length()
dub = [[0] * n for _ in range(m)]
for i, x in enumerate(a):
	if i == idx[x][-1]:
		dub[0][i] = n + idx[x][0] - i
	else:
		dub[0][i] = idx[x][bisect(idx[x], i)] - i
# print(dub[0])
for i in range(m - 1):
	for j in range(n):
		dub[i + 1][j] = dub[i][j] + 1 + dub[i][(j + dub[i][j] + 1) % n]
# print(dub)
now = -1
for i in range(m - 1, -1, -1):
	if now + 1 + dub[i][(now + 1) % n] <= n * k:
		now += 1 + dub[i][(now + 1) % n]
# print(now)
if now == n * k:
	print("")
	exit()
b = a[(now + 1) % n:]
# print(b)
inQ = {x: False for x in b}
Q = []
for x in b:
	if inQ[x]:
		while Q[-1] != x:
			inQ[Q.pop()] = False
		Q.pop()
		inQ[x] = False
	else:
		inQ[x] = True
		Q.append(x)
print(" ".join(map(str, Q)))

Submission status: Wrong Answer

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

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

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

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

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

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

print(*answer)
# 14

Submission status: Wrong Answer

Solution code:
from collections import deque


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



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

k_time = k
aa = a + a
next_ind = [-1] * (2 * n)
tmp_memo = {}
for i in range(2 * n)[::-1]:
    if aa[i] not in tmp_memo:
        tmp_memo[aa[i]] = i + 1
    else:
        next_ind[i] = tmp_memo[aa[i]]
        tmp_memo[aa[i]] = i + 1

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

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

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

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

Submission status: Wrong Answer

Solution code:
from collections import deque


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



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

k_time = k
aa = a + a
next_ind = [-1] * (2 * n)
tmp_memo = {}
for i in range(2 * n)[::-1]:
    if aa[i] not in tmp_memo:
        tmp_memo[aa[i]] = i + 1
    else:
        next_ind[i] = tmp_memo[aa[i]]
        tmp_memo[aa[i]] = i + 1

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

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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]]]
  print(*ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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




print(*ans, sep = ' ')

Submission status: Wrong Answer

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




print(*ans, sep = ' ')

Submission status: Wrong Answer

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:
            while ans[-1] != a:
                anss.remove(ans[-1])
                ans.pop()
            anss.remove(a)
            ans.pop()
        else:
            anss.add(a)
            ans.append(a)
    print(*ans)

Submission status: Wrong Answer

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

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

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

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

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