Submission #552472

#	Time	Username	Problem	Language	Result	Execution time	Memory
552472		jh05013	버블 정렬 (OJUZ10_bubblesort)	Pypy 3	100 / 100	899 ms	37184 KiB

bubblesort

MIS = lambda: map(int,input().split())

def compress(L):
    L = list(L)
    d = {}
    for i, x in enumerate(sorted(L)): d[x] = i
    return list(map(d.__getitem__, L))

class Fenwick:
    def __init__(_, size): _.arr = [0]*size
    def add(_, i, val):
        while i < len(_.arr): _.arr[i] += val; i |= i+1
    def getsum(_, i):
        res = 0
        while i >= 0: res+= _.arr[i]; i = (i&(i+1))-1
        return res
    def intersum(_, i, j): return _.getsum(j) - _.getsum(i-1)

n, k = MIS()
orig = list(MIS())
L = compress(orig)
F = Fenwick(n)

pos = []
for i, x in enumerate(L):
    pos.append(i - min(k, F.intersum(x+1, n-1)))
    F.add(x, 1)

# TODO optimize...
L = []
for i in range(n): L.insert(pos[i], orig[i])
print(*L)

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 47 / 47
• Subtask 4: 19 / 19