Submission #1150818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150818		jim_x	Job Scheduling (CEOI12_jobs)	Pypy 3	0 / 100	915 ms	131072 KiB

jobs

from typing import List, Tuple

N, D, M = 0, 0, 0

def is_feasible(jobs: List[Tuple[int, int]], machine_count: int) -> Tuple[bool, List[List[int]]]:
    schedule = [[] for _ in range(N)]
    req_num = 0
    for day in range(1, N + 1):
        for j 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 False, schedule

            if req_num == M:
                return True, schedule
    return False, 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 36%)

=======

• Subtask 1: 0 / 100