Problem p02964 (python)

Fixed submission:
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:
    if K==1:
        print(*A)
    else:
        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)

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
N,K = map(int,input().split())
A = list(map(int,input().split()))

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)

Buggy submission (verdict: Runtime Error):
N,K = map(int,input().split())
A = list(map(int,input().split()))

AA = A+A
last_i = {}
dp = [[0] for i in range(N)]
for i,a in enumerate(reversed(AA)):
    i = 2*N-i-1
    if i < N:
        dp[i][0] = last_i[a] - i + 1
    last_i[a] = i

MAX = N*K
k = 0
while (1<<k) <= MAX:
    for i in range(N):
        d,m = divmod(dp[i][k]+i, N)
        v = dp[m][k]
        dp[i].append(v + d*N+m-i)
    k += 1

def jump(k):
    j = x = 0
    while (1<<x) <= k:
        if k&(1<<x):
            j += dp[j%N][x]
            if j > MAX:
                return MAX+1
        x += 1
    return j

ok = 0
ng = MAX
while ng-ok > 1:
    m = (ok+ng)//2
    j = jump(m)
    if j <= MAX:
        ok = m
    else:
        ng = m

s = jump(ok)%N
if s==0:
    print()
else:
    ans = []
    anss = set()
    for a in A[s:]:
        if a in anss:
            anss.remove(a)
            while ans[-1] != a:
                ans.pop()
            ans.pop()
        else:
            anss.add(a)
            ans.append(a)
    print(*ans)

Buggy submission (verdict: Runtime Error):
N,K = map(int,input().split())
A = list(map(int,input().split()))

AA = A+A
last_i = {}
dp = [[0] for i in range(N)]
for i,a in enumerate(reversed(AA)):
    i = 2*N-i-1
    if i < N:
        dp[i][0] = last_i[a] - i + 1
    last_i[a] = i

MAX = N*K
k = 0
while (1<<k) <= MAX:
    for i in range(N):
        d,m = divmod(dp[i][k]+i, N)
        v = dp[m][k]
        dp[i].append(v + d*N+m-i)
    k += 1

def jump(k):
    j = x = 0
    while (1<<x) <= k:
        if k&(1<<x):
            j += dp[j%N][x]
            if j > MAX:
                return MAX+1
        x += 1
    return j

ok = 0
ng = MAX
while ng-ok > 1:
    m = (ok+ng)//2
    j = jump(m)
    if j <= MAX:
        ok = m
    else:
        ng = m

s = jump(ok)%N
if s==0:
    print()
else:
    ans = []
    anss = set()
    for a in A[s:]:
        if a in anss:
            anss.remove(a)
            while ans[-1] != a:
                ans.pop()
            ans.pop()
        else:
            anss.add(a)
            ans.append(a)
    print(*ans)

Buggy submission (verdict: Runtime Error):
N,K = map(int,input().split())
A = list(map(int,input().split()))

AA = A+A
last_i = {}
dp = [[0] for i in range(N)]
for i,a in enumerate(reversed(AA)):
    i = 2*N-i-1
    if i < N:
        dp[i][0] = last_i[a] - i + 1
    last_i[a] = i

MAX = N*K
k = 0
while (1<<k) <= MAX:
    for i in range(N):
        d,m = divmod(dp[i][k]+i, N)
        v = dp[m][k]
        dp[i].append(v + d*N+m-i)
    k += 1

def jump(k):
    j = x = 0
    while (1<<x) <= k:
        if k&(1<<x):
            j += dp[j%N][x]
            if j > MAX:
                return MAX+1
        x += 1
    return j

ok = 0
ng = MAX
jp = 0
while ng-ok > 1:
    m = (ok+ng)//2
    j = jump(m)
    if j <= MAX:
        ok = m
        jp = j
    else:
        ng = m
s = jp%N
if s==0:
    print()
else:
    ans = []
    anss = set()
    for a in A[s:]:
        if a in anss:
            anss.remove(a)
            while ans[-1] != a:
                ans.pop()
            ans.pop()
        else:
            anss.add(a)
            ans.append(a)
    print(*ans)