Submission #1281481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281481		osser	Job Scheduling (CEOI12_jobs)	Pypy 3	0 / 100	359 ms	72784 KiB

jobs

import sys
from array import array

# -------- быстрый ввод целых --------
def read_ints():
    data = sys.stdin.buffer.read()
    x = 0
    sign = 1
    in_num = False
    for b in data:
        if 48 <= b <= 57:          # '0'..'9'
            x = x * 10 + (b - 48)
            in_num = True
        else:
            if in_num:
                yield sign * x
                x = 0
                sign = 1
                in_num = False
            if b == 45:            # '-'
                sign = -1
    if in_num:
        yield sign * x

it = read_ints()
N = next(it)         # число дней
D = next(it)         # допустимая задержка
M = next(it)         # количество заявок

# -------- считываем дни подачи S[i] и считаем по дням --------
# S держим в компактном виде
S = array('I', [0]) * M
cnt = array('I', [0]) * (N + 2)    # cnt[d] = сколько заявок пришло в день d
for i in range(M):
    s = next(it)
    S[i] = s
    cnt[s] += 1

# -------- строим «отсортированный» по дням порядок заявок (bucket sort) --------
start = array('I', [0]) * (N + 2)  # начало блока дня d
acc = 0
for d in range(1, N + 1):
    start[d] = acc
    acc += cnt[d]

# Плоские массивы одинаковой длины M:
# arrivals[k] = день подачи k-й заявки в отсортированном порядке
# ids[k]      = номер заявки (1..M) в том же порядке
arrivals = array('I', [0]) * M
ids      = array('I', [0]) * M
cur = array('I', start)            # текущая позиция записи для каждого дня

for idx, s in enumerate(S, 1):
    p = cur[s]
    arrivals[p] = s
    ids[p] = idx
    cur[s] += 1

# -------- проверка осуществимости для K машин (ровно как в объяснении) --------
def feasible(K: int) -> bool:
    """
    Идём по дням 1..N; в каждый день выполняем до K заявок,
    беря их в порядке возрастания дня подачи (эквивалент EDF).
    Если встречаем заявку с s + D < day, дедлайн нарушен — K недостаточно.
    """
    req = 0  # указатель на следующую невыполненную заявку в (arrivals, ids)
    for day in range(1, N + 1):
        used = 0
        # можно брать только те, что уже пришли: arrivals[req] <= day
        while used < K and req < M and arrivals[req] <= day:
            s = arrivals[req]
            if s + D < day:        # этот job уже просрочен сегодня
                return False
            req += 1
            used += 1
        # если следующая заявка ещё не пришла — машины простаивают, это допустимо
    return req == M  # все ли успели выполнить к концу N-го дня?

# -------- печать расписания для найденного минимального K (без хранения целиком) --------
def emit_schedule(K: int):
    out = sys.stdout.write
    req = 0
    for day in range(1, N + 1):
        taken = 0
        first = True
        while taken < K and req < M and arrivals[req] <= day:
            # после успешной проверки дедлайнов здесь уже нарушений не будет
            if first:
                out(str(ids[req]))
                first = False
            else:
                out(" " + str(ids[req]))
            req += 1
            taken += 1
        if first:
            out("0\n")          # в этот день ничего не выполняли
        else:
            out(" 0\n")         # список ID + завершающий 0

# -------- бинпоиск по числу машин K в диапазоне [1, M] --------
lo, hi = 1, M
while lo < hi:
    mid = (lo + hi) // 2
    if feasible(mid):
        hi = mid
    else:
        lo = mid + 1

# -------- вывод результата --------
sys.stdout.write(str(lo) + "\n")
emit_schedule(lo)

Compilation message (stdout)

Compiling 'jobs.py'...

=======
  adding: __main__.pyc (deflated 36%)

=======

• Subtask 1: 0 / 100