Submission #1083782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083782		NEMO_	Job Scheduling (CEOI12_jobs)	Cpython 3	0 / 100	515 ms	65536 KiB

jobs

import heapq
from collections import defaultdict

def schedule_jobs(N, D, M, job_submissions):
    job_queue = []
    job_schedule = defaultdict(list)
    max_machines = 0
    submission_days = defaultdict(list)

    # Organize job submissions by day
    for i, day in enumerate(job_submissions, 1):
        submission_days[day].append(i)

    for day in range(1, N + 1):
        # Add new job submissions to the priority queue
        for job in submission_days[day]:
            heapq.heappush(job_queue, (day + D, job))

        # Process jobs for the current day
        machines_used = 0
        while job_queue and machines_used < len(job_queue):
            deadline, job = heapq.heappop(job_queue)
            if day <= deadline:
                job_schedule[day].append(job)
                machines_used += 1
            else:
                return None, None  # Impossible to schedule within the delay constraint

        max_machines = max(max_machines, machines_used)

    return max_machines, job_schedule

def main():
    # Read input
    N, D, M = map(int, input().split())
    job_submissions = list(map(int, input().split()))

    # Schedule jobs
    max_machines, schedule = schedule_jobs(N, D, M, job_submissions)

    # Output results
    if max_machines is None:
        print("Impossible to schedule within the given delay constraint.")
    else:
        print(max_machines)
        for day in range(1, N + 1):
            print(*schedule[day], 0)

if __name__ == "__main__":
    main()

• Subtask 1: 0 / 100