Submission #592310

#	Time	Username	Problem	Language	Result	Execution time	Memory
592310		54skyxenon	Job Scheduling (CEOI12_jobs)	Cpython 3	60 / 100	1085 ms	65536 KiB

jobs

# https://oj.uz/problem/view/CEOI12_jobs

from collections import defaultdict

n, d, m = map(int, input().split())

requests_by_day = defaultdict(list)
for req_iq, day in enumerate(map(int, input().split())):
    requests_by_day[day].append(req_iq + 1)

requests = sorted(requests_by_day.items())

# does `mid` number of machines work?
def ok(mid):
    requests_here = [(req[0], req[1][:]) for req in requests]

    schedule = []
    leftover = mid
    curr_day = 1
    
    i = 0
    curr_day_schedule = []
    while i < len(requests_here):
        if curr_day < requests_here[i][0]:
            curr_day += 1
            continue
        
        if curr_day - requests_here[i][0] > d:
            return False

        if leftover >= len(requests_here[i][1]):
            curr_day_schedule.extend(requests_here[i][1][:])
            leftover -= len(requests_here[i][1])
            requests_here[i][1].clear()
        else:
            for _ in range(leftover):
                curr_day_schedule.append(requests_here[i][1].pop())
            schedule.append(curr_day_schedule)
            curr_day_schedule = []
            leftover = mid
            curr_day += 1
            i -= 1

        i += 1

    if curr_day_schedule:
        schedule.append(curr_day_schedule)

    return schedule

# O(log M * (N + M))
def bs(lo, hi):
    hi += 1
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid
        else:
            lo = mid + 1

    return lo, ok(lo)

ans_len, ans = bs(1, m)
print(ans_len)

for i in range(n):
    if i >= len(ans):
        print(0)
    else:
        ans[i].append(0)
        print(' '.join(map(str, ans[i])))

• Subtask 1: 60 / 100