Skip to content

Instantly share code, notes, and snippets.

@giantonia
Created December 16, 2016 14:17
Show Gist options
  • Save giantonia/3ddbacddc7bd58b220ab592f802d9602 to your computer and use it in GitHub Desktop.
Save giantonia/3ddbacddc7bd58b220ab592f802d9602 to your computer and use it in GitHub Desktop.
# python3
def parent_key_cal(key):
if key % 2 == 0:
parent_key = (key - 2)//2
else:
parent_key = (key - 1)//2
return parent_key
def swap(alist, key1, key2):
temp = alist[key1]
alist[key1] = alist[key2]
alist[key2] = temp
def siftdown(alist, key):
parent = alist[key][1]
while len(alist) - 1 >= 2 * key + 1:
left = alist[2 * key + 1][1]
right = -1
if len(alist) - 1 >= 2 * key + 2:
right = alist[2 * key + 2][1]
if parent > left or (parent > right and right >= 0):
if left < right:
swap(alist, key, 2 * key + 1)
key = 2 * key + 1
elif left > right:
swap(alist, key, 2 * key + 2)
key = 2 * key + 2
else:
index_left = alist[2 * key + 1][0]
index_right = alist[2 * key + 2][0]
if index_left < index_right:
swap(alist, key, 2 * key + 1)
key = 2 * key + 1
else:
swap(alist, key, 2 * key + 2)
key = 2 * key + 2
elif parent == left or parent == right:
if left == right:
if alist[key][0] > alist[2 * key + 1][0] and alist[2 * key + 1][0] < alist[2 * key + 2][0]:
swap(alist, key, 2 * key + 1)
key = 2 * key + 1
elif alist[key][0] > alist[2 * key + 2][0] and alist[2 * key + 1][0] > alist[2 * key + 2][0]:
swap(alist, key, 2 * key + 2)
key = 2 * key + 2
else:
break
elif parent == left:
if alist[2 * key + 1][0] < alist[key][0]:
swap(alist, key, 2 * key + 1)
key = 2 * key + 1
else:
break
elif parent == right:
if alist[2 * key + 2][0] < alist[key][0]:
swap(alist, key, 2 * key + 2)
key = 2 * key + 2
else:
break
else:
break
else:
break
def siftup(alist, key):
child = alist[key][1]
parent_key = parent_key_cal(key)
parent = alist[parent_key][1]
while child < parent or (child == parent and alist[key][0] < alist[parent_key][0]):
if child < parent:
swap(alist, key, parent_key)
if parent_key != 0:
key = parent_key
parent_key = parent_key_cal(parent_key)
child = alist[key][1]
parent = alist[parent_key][1]
else:
break
else:
if alist[key][0] < alist[parent_key][0]:
swap(alist, key, parent_key)
key = parent_key
parent_key = parent_key_cal(parent_key)
child = alist[key][1]
parent = alist[parent_key][1]
def heap_insert(alist, value):
alist.append(value)
siftup(alist, len(alist) - 1)
line1 = input().split()
n = int(line1[0])
m = int(line1[1])
jobs = list(map(int, input().split()))
threads = []
for i in range(n):
threads.append([i, 0])
time = 0
record = []
while len(jobs) > 0:
if threads[0][1] <= time:
record.append([threads[0][0], time])
threads[0][1] += jobs[0]
swap(threads, 0, n - 1)
a = threads.pop()
siftdown(threads, 0)
heap_insert(threads, a)
jobs.pop(0)
else:
time += 1
for i in range(m):
print(str(record[i][0]) + ' ' + str(record[i][1]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment