답안 #552472

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
552472	2022-04-23T08:13:36 Z	jh05013	버블 정렬 (OJUZ10_bubblesort)	PyPy 3	100 / 100	899 ms	37184 KB

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.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	18244 KB	Output is correct
2	Correct	35 ms	18224 KB	Output is correct
3	Correct	35 ms	18160 KB	Output is correct
4	Correct	36 ms	18176 KB	Output is correct
5	Correct	43 ms	18152 KB	Output is correct
6	Correct	46 ms	18236 KB	Output is correct
7	Correct	35 ms	18212 KB	Output is correct

Subtask #2

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	96 ms	23252 KB	Output is correct
2	Correct	60 ms	19324 KB	Output is correct
3	Correct	52 ms	19008 KB	Output is correct
4	Correct	75 ms	22744 KB	Output is correct
5	Correct	80 ms	22688 KB	Output is correct
6	Correct	89 ms	22792 KB	Output is correct
7	Correct	79 ms	22772 KB	Output is correct
8	Correct	81 ms	22604 KB	Output is correct
9	Correct	107 ms	22904 KB	Output is correct
10	Correct	74 ms	22848 KB	Output is correct

Subtask #3

47.0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	800 ms	37000 KB	Output is correct
2	Correct	195 ms	36480 KB	Output is correct
3	Correct	460 ms	36740 KB	Output is correct
4	Correct	848 ms	36428 KB	Output is correct
5	Correct	678 ms	36456 KB	Output is correct
6	Correct	141 ms	30212 KB	Output is correct
7	Correct	795 ms	36472 KB	Output is correct
8	Correct	235 ms	36492 KB	Output is correct
9	Correct	208 ms	36504 KB	Output is correct
10	Correct	486 ms	37184 KB	Output is correct
11	Correct	233 ms	37020 KB	Output is correct
12	Correct	457 ms	36144 KB	Output is correct
13	Correct	682 ms	36976 KB	Output is correct
14	Correct	187 ms	37040 KB	Output is correct
15	Correct	551 ms	37040 KB	Output is correct

Subtask #4

19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	194 ms	35332 KB	Output is correct
2	Correct	209 ms	35328 KB	Output is correct
3	Correct	476 ms	33104 KB	Output is correct
4	Correct	500 ms	35200 KB	Output is correct
5	Correct	899 ms	35228 KB	Output is correct
6	Correct	225 ms	35256 KB	Output is correct
7	Correct	865 ms	35276 KB	Output is correct
8	Correct	139 ms	28468 KB	Output is correct
9	Correct	709 ms	35264 KB	Output is correct
10	Correct	515 ms	35304 KB	Output is correct
11	Correct	815 ms	35320 KB	Output is correct
12	Correct	186 ms	35264 KB	Output is correct
13	Correct	691 ms	35220 KB	Output is correct
14	Correct	493 ms	33804 KB	Output is correct
15	Correct	185 ms	35288 KB	Output is correct