Submission #1088563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088563		vjudge1	Job Scheduling (CEOI12_jobs)	Cpython 3	0 / 100	1089 ms	65536 KiB

jobs

from collections import defaultdict

def pode_processar_todos(N, D, M, sol, num_mas):
    cron = [[] for _ in range(N + 1)]
    sol_dia = defaultdict(list)

    for idx, s in enumerate(sol):
        sol_dia[s].append(idx + 1)

    for dia in range(1, N + 1):
        sol_hoje = sol_dia[dia]
        for i in range(dia, min(N + 1, dia + D + 1)):
            while sol_hoje and len(cron[i]) < num_mas:
                cron[i].append(sol_hoje.pop(0))

    todos_agendados = all(len(sol_dia[dia]) == 0 for dia in range(1, N + 1))
    return todos_agendados, cron

def encontrar_min_mas(N, D, M, sol):
    esq, dir = 1, max(sol.count(i) for i in range(1, N + 1))

    while esq < dir:
        meio = (esq + dir) // 2
        viavel, _ = pode_processar_todos(N, D, M, sol, meio)
        if viavel:
            dir = meio
        else:
            esq = meio + 1

    return esq

def agendar_trabalhos(N, D, M, sol):
    min_mas = encontrar_min_mas(N, D, M, sol)
    _, cron = pode_processar_todos(N, D, M, sol, min_mas)

    print(min_mas)
    for dia in range(1, N + 1):
        if cron[dia]:
            print(' '.join(map(str, cron[dia])) + ' 0')
        else:
            print('0')

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

• Subtask 1: 0 / 100