Submission #1250829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250829		caterpillow	Job Scheduling (CEOI12_jobs)	Pypy 3	0 / 100	1100 ms	131072 KiB

jobs

from queue import Queue

def check(mid):
    todo = Queue()
    j = 0
    sol = [[] for i in range(n)]
    for i in range(n):
        while j < m and reqs[ord[j]] == i:
            todo.put(ord[j])
            j += 1
        for k in range(mid):
            if todo.empty():
                break
            if i - reqs[todo.queue[0]] > d:
                return []
            sol[i].append(todo.queue[0])
            todo.get()
    if not todo.empty():
        return []
    return sol

n, d, m = map(int, input().split())
reqs = list(map(int, input().split()))
for i in range(m):
    reqs[i] -= 1
ord = [i for i in range(m)]
ord.sort(key = lambda x: reqs[x])

lo, hi = 0, m
while hi - lo > 1:
    mid = (lo + hi) // 2
    if len(check(mid)):
        hi = mid
    else:
        lo = mid
print(hi)
sol = check(hi)
for i in range(n):
    for j in sol[i]:
        print(j + 1, end=' ')
    print(0)

Compilation message (stdout)

Compiling 'jobs.py'...

=======
  adding: __main__.pyc (deflated 40%)

=======

• Subtask 1: 0 / 100