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: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
N,K = map(int,input().split())
A = list(map(int,input().split()))

#N = 2*10**5
#K = 10**12
#A = [(i % 200000) + 1 for i in range(N)]

def answer(N,K,A):
    s = []
    for i in range(N*K):
        a = A[i%N]
        if a in s:
            s = s[:s.index(a)]
        else:
            s.append(a)
    return s

def solve(N,K,A):
    B = A * 2
    NA = [-1]*N
    d = {}
    for i, b in enumerate(B):
        if b in d:
            if NA[d[b]%N] == -1:
                NA[d[b]%N] = i - d[b]+1
            d[b] = i 
        else:
            d[b] = i

    L = 57
    ds = [NA]
    for i in range(L):
        pre = ds[-1]
        temp = [pre[j] + pre[(pre[j]+j)%N] for j in range(N)]
        ds.append(temp)

    cnt = 0
    i = 0

    L -= 1
    NA = ds[L]
    while True:
        add = NA[i]
        nxt = ((i + add)%N)
        if cnt + add > N*K:
            L -= 1
            if L < 0:
                break
            NA = ds[L]
            continue
        cnt += add
        i = nxt

    rest = N*K - cnt

    s = []
    NA = ds[0]
    for j in range(rest):
        a = A[i%N]
        if a in s:
            s = s[:s.index(a)]
        else:
            s.append(a)
        i += 1
    return s

print(*solve(N,K,A))
#import random
#N,K = 2*10**5,2*10**5
#A = [random.randint(1,2*10**5) for i in range(N)]
#solve(N,K,A)
#exit()
#for i in range(100):
#    import random
#    N,K = 100,100
#    A = [random.randint(1,10) for i in range(N)]
#    s1 = answer(N,K,A)
#    s2 = solve(N,K,A)
#    if s1 != s2:
#        print(N,K,A)
#        print(s1)
#        print(s2)
#        break

Submission status: Time Limit Exceeded

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(mapint())
double_As = As*2
idx_dic = {}
idx_lis = [N+1]*(2*N)
for i in range(N*2-1, -1, -1):
    a = double_As[i]
    if a in idx_dic:
        idx_lis[i] = idx_dic[a]+1
    idx_dic[a] = i
doubling = [[0]*N for _ in range(100)]
accum = [[0]*N for _ in range(100)]
doubling[0] = [i%N for i in idx_lis[:N]]
accum[0] = [a-i for i, a in enumerate(idx_lis[:N])]
for i in range(1, 100):
    for j in range(N):
        doubling[i][j] = doubling[i-1][doubling[i-1][j]]
        accum[i][j] = accum[i-1][j] + accum[i-1][doubling[i-1][j]]
now = 0
cum = 0
cnt = 0
for i in range(99, -1, -1):
    if cum + accum[i][now]>N*K:
        continue
    else:
        cum += accum[i][now]
        now = doubling[i][now]
ans = []
while cum<N*K:
    if cum+accum[0][now]<=N*K:
        cum += accum[0][now]
        now = doubling[0][now]
    else:
        ans.append(As[now])
        now += 1
        cum += 1
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    N, K = LI()
    A = LI()
    maxA = max(A)

    def function(s):
        stack = deque()
        num = [0]*(maxA+1)
        for i in range(s,N):
            a = A[i]
            if num[a]==0:
                stack.append(a)
                num[a] += 1
            else:
                while(num[a]>0):
                    num[stack.pop()] -= 1

        return stack

    B = [-1 for _ in range(N)]
    que = {}
    for i in range(N):
        a = A[i]
        if a not in que:
            que[a] = i
        else:
            prev = que.pop(a)
            B[prev] = i - prev
            que[a] = i
    i = 0
    while(que):
        a = A[i]
        if a in que:
            prev = que.pop(a)
            B[prev] = N + i - prev
        i += 1
    #print(B)
    locat_doubling = [[-1]*N for _ in range(61)]

    for i in range(N):
        locat_doubling[0][i] = 0
        locat_doubling[1][i] = B[i] + 1

    for k in range(2,61):
        for i in range(N):
            locat_doubling[k][i] = locat_doubling[k-1][i] + locat_doubling[k-1][(i+locat_doubling[k-1][i])%N]
    #print(locat_doubling[:5])
    now = 0
    rest = K*N
    for i in range(61)[::-1]:
        if locat_doubling[i][now]<=rest:
            rest -= locat_doubling[i][now]
            now = (locat_doubling[i][now]+now)%N
    #print(rest,now)

    ans = function(now)
    print(" ".join(map(str,ans)))
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examB()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Time Limit Exceeded

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


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

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

    conv = [0] * (N+1)
    for i, j in enumerate(A):
        pos = i

        while pos < N:
            v = A[pos]
            p = bisect_right(dd[v], pos)
            size = len(dd[v])
            if p < size:
                pos = dd[v][p]+1
                if pos == N:
                    conv[i] = 0
                    break
            else:
                conv[i] = dd[A[pos]][0] + 1
                break
    conv[N] = 0

    dp = [[0]*(N+1) for _ in range(41)]
    for i in range(N+1):
        dp[0][i] = conv[i]

    for k in range(1, 41):
        for n in range(N+1):
            dp[k][n] = dp[k - 1][dp[k - 1][n]]

    res = []
    t = K-1
    for i in range(41):
        if (t>>i)&1:
            res.append(i)
        
    pos = 0
    for i in res:
        pos = dp[i][pos]

    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)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
from collections import defaultdict

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

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

conv = [0] * (N+1)
for i, j in enumerate(A):
    pos = i

    while pos < N:
        v = A[pos]
        p = bisect_right(dd[v], pos)
        size = len(dd[v])
        if p < size:
            pos = dd[v][p]+1
            if pos == N:
                conv[i] = 0
                break
        else:
            conv[i] = dd[A[pos]][0] + 1
            break
conv[N] = 0

dp = [[0]*(N+1) for _ in range(60)]
for i in range(N+1):
    dp[0][i] = conv[i]

for k in range(1, 60):
    for n in range(N+1):
        dp[k][n] = dp[k - 1][dp[k - 1][n]]

res = []
t = K-1
for i in range(60):
    if (t>>i)&1:
        res.append(i)
    
pos = 0
for i in res:
    pos = dp[i][pos]

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: Time Limit Exceeded

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)

if i==1:
    print(ans[0])
else:
    print(ans[K%(i-1)-1])

Submission status: Time Limit Exceeded

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,k = map(int,ipt().split())
    a = list(map(int,ipt().split()))
#    n = 2*10**5
#    k = 2*10**5
#    a = [i+1 for i in range(n)]
    nxt = [-1]*(n)
    pa = [-1]*(2*10**5+1)
    for i,ai in enumerate(a*2):
        pai = pa[ai]
        if pai == -2:
            continue
        if pai == -1:
            pa[ai] = i
        else:
            nxt[pai] = i-pai+1
            if i <= n-1:
                pa[ai] = i
            else:
                pa[ai] = -2
    dbl = [nxt]
    ni = 1
    while ni <= n*k:
        nnxt = [0]*n
        pnxt = dbl[-1]
        for i in range(n):
            nnxt[i] = pnxt[i]+pnxt[(i+pnxt[i])%n]
        dbl.append(nnxt)
        if min(nnxt) > n*k:
            break
        ni *= 2
    np = 0
    ld = len(dbl)
    ni = len(dbl)-1
#    print(dbl)
    for db in dbl[::-1]:
        while True:
            if db[np%n] < n*k-1-np:
                np += db[np%n]
            else:
                break
#        print(np)
    ans = []
    np %= n
    while np < n:
        if nxt[np]+np > n:
            ans.append(a[np])
            np += 1
        elif nxt[np]+np == n:
            np = n
        else:
            np = nxt[np]+np
    print(" ".join(map(str,ans)))



    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,k = map(int,ipt().split())
    a = list(map(int,ipt().split()))
#    n = 2*10**5
#    k = 2*10**5
#    a = [i+1 for i in range(n)]
    nxt = [-1]*(n)
    pa = [-1]*(2*10**5+1)
    for i,ai in enumerate(a*2):
        pai = pa[ai]
        if pai == -2:
            continue
        if pai == -1:
            pa[ai] = i
        else:
            nxt[pai] = i-pai+1
            if i <= n-1:
                pa[ai] = i
            else:
                pa[ai] = -2
    dbl = [nxt]
    ni = 1
    while ni <= n*k:
        nnxt = [0]*n
        pnxt = dbl[-1]
        for i in range(n):
            nnxt[i] = pnxt[i]+pnxt[(i+pnxt[i])%n]
        dbl.append(nnxt)
        if min(nnxt) > n*k:
            break
        ni *= 2
    np = 0
    ld = len(dbl)
    ni = len(dbl)-1
#    print(dbl)
    for db in dbl[::-1]:
        while True:
            if db[np%n] < n*k-1-np:
                np += db[np%n]
            else:
                break
#        print(np)
    ans = []
    for i in range(np%n,n):
        ai = a[i]
        if ai in ans:
            ans = ans[:ans.index(ai)]
        else:
            ans.append(ai)
    print(" ".join(map(str,ans)))



    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,k = map(int,ipt().split())
    a = list(map(int,ipt().split()))
#    n = 2*10**5
#    k = 2*10**5
#    a = [i+1 for i in range(n)]
    nxt = [-1]*(n)
    pa = [-1]*(2*10**5+1)
    for i,ai in enumerate(a*2):
        pai = pa[ai]
        if pai == -2:
            continue
        if pai == -1:
            pa[ai] = i
        else:
            nxt[pai] = i-pai+1
            if i <= n-1:
                pa[ai] = i
            else:
                pa[ai] = -2
    dbl = [nxt]
    ni = 1
    while ni <= n*k:
        nnxt = [0]*n
        pnxt = dbl[-1]
        for i in range(n):
            nnxt[i] = pnxt[i]+pnxt[(i+pnxt[i])%n]
        dbl.append(nnxt)
        if min(nnxt) > n*k:
            break
        ni *= 2
    np = 0
    ld = len(dbl)
    ni = len(dbl)-1
#    print(dbl)
    while ni >= 0:
        db = dbl[ni]
        if db[np%n] < n*k-1-np:
            np += db[np%n]
        else:
            ni -= 1
#        print(np)
    ans = []
    for i in range(np%n,n):
        ai = a[i]
        if ai in ans:
            ans = ans[:ans.index(ai)]
        else:
            ans.append(ai)
    print(" ".join(map(str,ans)))



    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,k = map(int,ipt().split())
    a = list(map(int,ipt().split()))
#    n = 2*10**5
#    k = 2*10**5
#    a = [i+1 for i in range(n)]
    nxt = [-1]*(n)
    pa = [-1]*(2*10**5+1)
    for i,ai in enumerate(a*2):
        pai = pa[ai]
        if pai == -2:
            continue
        if pai == -1:
            pa[ai] = i
        else:
            nxt[pai] = i-pai+1
            if i <= n-1:
                pa[ai] = i
            else:
                pa[ai] = -2
    dbl = [nxt]
    ni = 1
    while ni <= n*k:
        nnxt = [0]*n
        pnxt = dbl[-1]
        for i in range(n):
            nnxt[i] = pnxt[i]+pnxt[(i+pnxt[i])%n]
        dbl.append(nnxt)
        ni *= 2
    np = 0
    ld = len(dbl)
    ni = len(dbl)-1
#    print(dbl)
    while ni >= 0:
        db = dbl[ni]
        if db[np%n] < n*k-1-np:
            np += db[np%n]
        else:
            ni -= 1
#        print(np)
    ans = []
    for i in range(np%n,n):
        ai = a[i]
        if ai in ans:
            ans = ans[:ans.index(ai)]
        else:
            ans.append(ai)
    print(" ".join(map(str,ans)))



    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

inds = {}
y = [0]*n

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

for lst in inds.values():
    y[lst[-1]] = n+lst[0]+1 - lst[-1]

length = (n*k).bit_length()

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

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]

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

Submission status: Time Limit Exceeded

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

inds = {}
y = [0]*n

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

for lst in inds.values():
    y[lst[-1]] = n+lst[0]+1 - lst[-1]

length = (n*k).bit_length()

db = {0: y}
for m in range(length):
    db[m+1] = [db[m][i] + db[m][(i+db[m][i]) % n] for i in range(n)]

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]

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

Submission status: Time Limit Exceeded

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

inds = {}
y = [0]*n

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

for lst in inds.values():
    y[lst[-1]] = n+lst[0]+1 - lst[-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]

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

Submission status: Time Limit Exceeded

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*2).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)


def last():
    cur = 0
    while True:
        for i in range(length+1):
            if cur + db[i][cur % n] > n*k:
                if i != 0:
                    cur += db[i-1][cur % n]
                    break
                else:
                    return cur


cur = last()

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]

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

Submission status: Time Limit Exceeded

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)


def last():
    cur = 0
    while True:
        for i in range(length+1):
            if cur + db[i][cur % n] > n*k:
                if i != 0:
                    cur += db[i-1][cur % n]
                    break
                else:
                    return cur


cur = last()

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]

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

Submission status: Time Limit Exceeded

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]

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

Submission status: Time Limit Exceeded

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)

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

cyc = k%(cnt//n)
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(cnt//n == cyc):
        cnt -= ind[now][right] - ind[now][right-1] + 1
        break
    now = a[cnt%n]

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

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

Submission status: Time Limit Exceeded

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

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

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

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

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

print(*stack)

Submission status: Time Limit Exceeded

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

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

zero = [-1 for i in range(n)]
for key, value in dic.items():
    num = len(value)
    for i in range(num-1):
        zero[value[i]] = value[i+1] - value[i] + 1
    zero[value[-1]] = n - value[-1] + value[0] + 1

lst = [zero]
while lst[-1][0] <+ n*k - 1:
    before = lst[-1]
    after = []
    for i in range(n):
        after.append(before[i] + before[(before[i]+i)%n])
    lst.append(after)
lst.pop()

i = 0
while lst != []:
    lsti = lst.pop()
    while True:
        if i + lsti[i%n] <= n*k - 1:
            i = i + lsti[i%n]
        else:
            break

i = i % n
nokori = a[i:]
lst = []
dic = {}
ko = 0
for i in range(len(nokori)):
    if nokori[i] not in dic:
        lst.append(nokori[i])
        dic[nokori[i]] = ko
        ko += 1
    else:
        lst = lst[:dic[nokori[i]]]
        dic = {}
        for j in range(len(lst)):
            dic[lst[j]] = j
        ko = len(lst)
print(*lst)

Submission status: Time Limit Exceeded

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

used = set()
stack = []
cnt = 0
while stack or cnt == 0:
    for e in a:
        if e in used:
            while stack[-1] != e:
                pp = stack.pop()
                used.remove(pp)

            stack.pop()
            used.remove(e)

        else:
            stack.append(e)
            used.add(e)

    cnt += 1

q, r = divmod(k, cnt)
for _ in range(r):
    for e in a:
        if e in used:
            while stack[-1] != e:
                pp = stack.pop()
                used.remove(pp)

            stack.pop()
            used.remove(e)

        else:
            stack.append(e)
            used.add(e)

print(*stack)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

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

li = []
used = set()
stack = []
cnt = 0
while stack or cnt == 0:
    for e in a:
        if e in used:
            while stack[-1] != e:
                pp = stack.pop()
                used.remove(pp)

            stack.pop()
            used.remove(e)

        else:
            stack.append(e)
            used.add(e)

    li.append(deepcopy(stack))
    cnt += 1

q, r = divmod(k, cnt)
ans = li[r-1]
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect
from collections import defaultdict
def main():
	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 = [[-1] * 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):
			if dub[i][j]<n*k and dub[i][j]!=-1:
				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 dub[i][(now+1)%n]!=-1 and 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)))

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect
from collections import defaultdict
def main():
	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)))

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

seq=0
answer_dic={0:tuple()}
answer_list=[]
for i in range(K):
  for a in alist:
    if not a in answer_list:
      answer_list.append(a)
    else:
      while(True):
        if a==answer_list.pop():
          break
  
  #print(i+1,answer_list)
  answer_dic[i+1]=tuple(answer_list)
  if len(answer_list)==0:
    seq=i+1
    break

if len(answer_list)>0:  
  print(*answer_list)
else:
  print(*answer_dic[K%seq])

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right as bisect
N, K = map(int, input().split())
A = list(map(int, input().split()))
m = max(A)
a_to_i = [[] for _ in range(m+1)]
for i in range(N):
    a_to_i[A[i]].append(i)
now = 0
next_k_i = [[None]*N for _ in range(60)]
for now in range(N):
    h = 0
    i = bisect(a_to_i[A[now]], now)
    if i == len(a_to_i[A[now]]):
        i = 0
        h+=N
    i = a_to_i[A[now]][i]
    h+=(i-now+1)
    next_k_i[1][now] = ((i+1)%N, h)
for i in range(2, 60):
    for j in range(N):
        a, b = next_k_i[i-1][j]
        c, d = next_k_i[i-1][a]
        next_k_i[i][j] = (c, b+d)
now = 0
cnt = K*N
while cnt:
    flag = False
    for i in range(1, 60)[::-1]:
        a, b = next_k_i[i][now]
        if cnt>=b:
            cnt-=b
            now = a
            flag = True
            break
    if not flag:
        break
ans = []
while now<N:
    a = next_k_i[1][now][0]
    if next_k_i[1][now][0] == 0:
        a+=N
    if a>now+1:
        now = a
        continue
    ans.append(A[now])
    now+=1
print(*ans)