P2Q.py

# 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]))