Submission #1281479

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

jobs

#MLE
def is_feasible(jobs,machine_count):
    schedule=[[] for _ in range(N)]
    req_num=0
    for day in range(1,N+1):
        for _ in range(machine_count):
            if jobs[req_num][0]>day:
                break
            if jobs[req_num][0]+D>=day:
                schedule[day-1].append(jobs[req_num][1])
                req_num+=1
            else:
                return 0,schedule
            if req_num==M:
                return 1,schedule
    return 0,schedule
def main():
    global N,D,M
    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()
    result=[]
    l,r=1,M
    while l<r:
        machine_num=(l+r)//2
        cur_result=is_feasible(jobs,machine_num)
        if cur_result[0]:
            r=machine_num
            result=cur_result[1]
        else:
            l=machine_num+1
    print(l)
    for i in range(N):
        for idx in result[i]:
            print(idx,end=" ")
        print(0)
main()

Compilation message (stdout)

Compiling 'jobs.py'...

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

=======

• Subtask 1: 0 / 100