oj.uz

Submission #730445

# Submission time Handle Problem Language Result Execution time Memory
730445 2023-04-25T22:37:29 Z iamjiamingliu Job Scheduling (CEOI12_jobs) Python 3
0 / 100
 1000 ms 65536 KB 
"""
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 + 1) 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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 22144 KB Time limit exceeded
2 Execution timed out 1084 ms 22152 KB Time limit exceeded
3 Execution timed out 1071 ms 22136 KB Time limit exceeded
4 Execution timed out 1084 ms 22108 KB Time limit exceeded
5 Execution timed out 1084 ms 22128 KB Time limit exceeded
6 Execution timed out 1077 ms 22144 KB Time limit exceeded
7 Execution timed out 1085 ms 22272 KB Time limit exceeded
8 Execution timed out 1060 ms 22096 KB Time limit exceeded
9 Execution timed out 1079 ms 31756 KB Time limit exceeded
10 Execution timed out 1077 ms 31740 KB Time limit exceeded
11 Incorrect 565 ms 24596 KB Unexpected end of file - int32 expected
12 Execution timed out 1074 ms 45088 KB Time limit exceeded
13 Execution timed out 1083 ms 65536 KB Time limit exceeded
14 Runtime error 271 ms 65536 KB Execution killed with signal 9
15 Runtime error 226 ms 65536 KB Execution killed with signal 9
16 Runtime error 184 ms 65536 KB Execution killed with signal 9
17 Runtime error 111 ms 65536 KB Execution killed with signal 9
18 Runtime error 78 ms 65536 KB Execution killed with signal 9
19 Runtime error 75 ms 65536 KB Execution killed with signal 9
20 Runtime error 116 ms 65536 KB Execution killed with signal 9