제출 #1088569

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1088569		vjudge1	Job Scheduling (CEOI12_jobs)	Cpython 3	0 / 100	1092 ms	65536 KiB

jobs

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

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

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

    # Verifica se todas as solicitações foram alocadas
    todos_agendados = all(not sol_dia[dia] 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):
        print(' '.join(map(str, cron[dia])) + ' 0' if cron[dia] else '0')

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

• Subtask 1: 0 / 100