oj.uz

Submission #730444

# Submission time Handle Problem Language Result Execution time Memory
730444 2023-04-25T22:35:04 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) 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 1068 ms 22436 KB Time limit exceeded
2 Execution timed out 1080 ms 22436 KB Time limit exceeded
3 Execution timed out 1083 ms 22448 KB Time limit exceeded
4 Execution timed out 1076 ms 22436 KB Time limit exceeded
5 Execution timed out 1064 ms 22348 KB Time limit exceeded
6 Execution timed out 1068 ms 22464 KB Time limit exceeded
7 Execution timed out 1062 ms 22436 KB Time limit exceeded
8 Execution timed out 1067 ms 22420 KB Time limit exceeded
9 Execution timed out 1084 ms 32096 KB Time limit exceeded
10 Execution timed out 1079 ms 31940 KB Time limit exceeded
11 Incorrect 567 ms 24932 KB Expected EOLN
12 Execution timed out 1071 ms 46004 KB Time limit exceeded
13 Execution timed out 1059 ms 65536 KB Time limit exceeded
14 Runtime error 249 ms 65536 KB Execution killed with signal 9
15 Runtime error 225 ms 65536 KB Execution killed with signal 9
16 Runtime error 164 ms 65536 KB Execution killed with signal 9
17 Runtime error 110 ms 65536 KB Execution killed with signal 9
18 Runtime error 71 ms 65536 KB Execution killed with signal 9
19 Runtime error 77 ms 65536 KB Execution killed with signal 9
20 Runtime error 103 ms 65536 KB Execution killed with signal 9