제출 #592304

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
592304		54skyxenon	Job Scheduling (CEOI12_jobs)	Cpython 3	40 / 100	1083 ms	65536 KiB

jobs

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

from copy import deepcopy
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 = deepcopy(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

def bs(lo, hi):
    mid = (lo + hi) // 2

    if not ok(mid):
        return bs(mid + 1, hi)
    elif mid > lo and ok(mid - 1):
        return bs(lo, mid - 1)
    else:
        return mid, ok(mid)

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: 40 / 100