oj.uz

Submission #1083782

# Submission time Handle Problem Language Result Execution time Memory
1083782 2024-09-04T06:34:44 Z NEMO_ Job Scheduling (CEOI12_jobs) Python 3
0 / 100
 515 ms 65536 KB 
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.0

# Verdict Execution time Memory Grader output
1 Incorrect 115 ms 15756 KB Expected integer, but "Impossible" found
2 Incorrect 125 ms 15656 KB Expected integer, but "Impossible" found
3 Incorrect 131 ms 15628 KB Expected integer, but "Impossible" found
4 Incorrect 151 ms 15580 KB Expected integer, but "Impossible" found
5 Incorrect 110 ms 15648 KB Expected integer, but "Impossible" found
6 Incorrect 110 ms 15624 KB Expected integer, but "Impossible" found
7 Incorrect 109 ms 15632 KB Expected integer, but "Impossible" found
8 Incorrect 109 ms 15756 KB Expected integer, but "Impossible" found
9 Incorrect 67 ms 9664 KB Expected integer, but "Impossible" found
10 Incorrect 118 ms 10184 KB Expected integer, but "Impossible" found
11 Incorrect 126 ms 14492 KB Output isn't correct
12 Incorrect 260 ms 25880 KB Output isn't correct
13 Runtime error 401 ms 36552 KB Memory limit exceeded
14 Runtime error 515 ms 52556 KB Memory limit exceeded
15 Runtime error 176 ms 60136 KB Memory limit exceeded
16 Runtime error 86 ms 65536 KB Execution killed with signal 9
17 Runtime error 66 ms 65536 KB Execution killed with signal 9
18 Runtime error 61 ms 65536 KB Execution killed with signal 9
19 Runtime error 60 ms 65536 KB Execution killed with signal 9
20 Runtime error 63 ms 65536 KB Execution killed with signal 9