Submission #1281490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281490		osser	Job Scheduling (CEOI12_jobs)	Pypy 3	0 / 100	977 ms	131072 KiB

jobs

import sys
input = sys.stdin.readline

N, D, M = map(int, input().split())
jobs = list(map(int, input().split()))
for i in range(M):
    jobs[i] = (jobs[i], i+1)
jobs.sort()

def is_feasible(m):
    schedule = [[] for _ in range(N)]
    j = 0

    for day in range(1, N+1):
        for _ in range(m):
            if jobs[j][0] > day:
                break

            if jobs[j][0] + D >= day:
                schedule[day-1].append(jobs[j][1])
                j += 1
            else:
                return 0, schedule
            
            if j == M:
                return 1, schedule
            
    return 0, schedule
    
ans = []
l, r = 1, M
while l < r:
    mid = (l + r) // 2
    result = is_feasible(mid)

    if result[0]:
        r = mid
        ans = result[1]
    else:
        l = mid + 1

print(l)
for i in range(N):
    ans[i] += [0]
    print(*ans[i])

Compilation message (stdout)

Compiling 'jobs.py'...

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

=======

• Subtask 1: 0 / 100