Submission #517318

#	Time	Username	Problem	Language	Result	Execution time	Memory
517318		perseverance201	Job Scheduling (CEOI12_jobs)	Cpython 3	0 / 100	1065 ms	65540 KiB

jobs

from pprint import pprint
n, d, m = list(map(int, input().strip().split()))
requests = list(map(int, input().strip().split()))
request_count = {}
for idx, request in enumerate(requests):
    if request in request_count:
        request_count[request].append(idx+1)
    else:
        request_count[request] = [idx+1]


def min_machine(x):
    pending_job = 0
    for day in range(1, n-d+1):
        pending_job += len(request_count.get(day, []))
        pending_job -= min(x, pending_job)
    if pending_job > 0:
        return False
    else:
        return True


def bin_search(low, high, f):
    while low < high:
        mid = low + (high-low)//2
        if f(mid):
            high = mid
        else:
            low = mid + 1
    return low

ans = bin_search(1, int(1e6), min_machine)
print(ans)
pending_job = []
ptr = 0
for day in range(1, n+1):
    pending_job += request_count.get(day, [])
    if ptr < len(pending_job):
        for i in range(ans):
            print(pending_job[ptr], end=' ')
            ptr += 1
        print(0)
    else:
        print(0)

• Subtask 1: 0 / 100