Submission #498187

#	Time	Username	Problem	Language	Result	Execution time	Memory
498187		arisja	Job Scheduling (CEOI12_jobs)	Cpython 3	0 / 100	1095 ms	65540 KiB

jobs

def f(ar, x, n, d, m):
    st = []
    new_req = 0
    for i in range(1, n + 1):
        st.append([])
        for j in range(x):
            if ar[new_req][0] > i:
                break
            if new_req + d >= i:
                #st += str(ar[new_req][1]) + ' '
                st[i-1].append(ar[new_req][1])
                new_req += 1
            else:
                return False, st
            if new_req == m:
                return True, st
    return False, st
            


def lower_bound(ar):
    global stor1
    l = 0
    r = len(ar)
    while r - l != 1:
        mid = (r + l) // 2
        stor = f(ar, mid, n, d, m)
        if stor[0]:
            r = mid
            stor1 = stor
        else:
            l = mid
    return r

stor1 =''
n, d, m = map(int, input().split())
ar = list(map(int, input().split()))
for i in range(m):
    ar[i] = [ar[i], i + 1]
ar.sort()
print(lower_bound(ar))
#print(stor1[1])
for i in range(n):
    if i >= len(stor1[1]):
        print('0')
    elif stor1[1][i] == []:
        print('0')
    else:
        print(" ".join(map(str, stor1[1][i])) + ' 0')

• Subtask 1: 0 / 100