Submission #590324

#	Time	Username	Problem	Language	Result	Execution time	Memory
590324		dnialh	Rope (JOI17_rope)	Pypy 3	80 / 100	1179 ms	262144 KiB

rope

from collections import Counter

import sys as sus
input = sus.stdin.readline

n, m = map(int, input().split())
c = list(map(int, input().split()))

ct = Counter(c)
o = ct.most_common()
odd = Counter()
eve = Counter()

for i in range(n - 1):
    if i % 2:
        odd[(c[i], c[i + 1])] += 1
    else:
        eve[(c[i], c[i + 1])] += 1

out = []
for i in range(1, m + 1):
    res = 0
    for v, vc in o:
        if v == i:
            continue

        bl = odd[(i, v)] + odd[(v, i)]
        br = eve[(i, v)] + eve[(v, i)]

        bad = min(bl, br)

        res = max(res, vc - bad)

        if bad == 0:
            break
    out.append(n - res - ct[i])
print('\n'.join(map(str, out)))

• Subtask 1: 15 / 15
• Subtask 2: 30 / 30
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 0 / 20