Submission #730444

#	Time	Username	Problem	Language	Result	Execution time	Memory
730444		iamjiamingliu	Job Scheduling (CEOI12_jobs)	Cpython 3	0 / 100	1084 ms	65536 KiB

jobs

"""
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
"""

from typing import NamedTuple


class Job(NamedTuple):
    day: int
    idx: int


days_cnt, max_delay, _ = map(int, input().split())
jobs = [Job(day, idx) for idx, day in enumerate(map(int, input().split()))]
jobs.sort()

max_repetition = 0
i = 0
while i < len(jobs):
    cur_repetition = 1
    while i + 1 < len(jobs) and jobs[i + 1].day == jobs[i].day:
        cur_repetition += 1
        i += 1
    i += 1
    max_repetition = max(max_repetition, cur_repetition)

l, r = 1, max_repetition + 1


def try_work(machines_cnt):
    cur_path = []
    job_i = 0
    for day in range(1, days_cnt + 1):
        if job_i == len(jobs):
            cur_path.extend([[] for _ in range(days_cnt - day)])
            break
        cur_day_work = []
        while len(cur_day_work) < machines_cnt and job_i < len(jobs) and jobs[job_i].day <= day:
            if day - jobs[job_i].day > max_delay:
                return False
            cur_day_work.append(jobs[job_i].idx)
            job_i += 1
        cur_path.append(cur_day_work)
    global path
    path = cur_path
    return True


path = []
while l < r:
    mid = (l + r) // 2
    if try_work(machines_cnt=mid):
        r = mid
    else:
        l = mid + 1

print(l)
for work_done_in_day in path:
    print(*work_done_in_day, 0)

• Subtask 1: 0 / 100