Submission #1281493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281493		osser	Job Scheduling (CEOI12_jobs)	Pypy 3	0 / 100	373 ms	72656 KiB

jobs

import sys
from array import array

# --- быстрый парсер целых из stdin без .split() ---
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: дни подачи (компактно)
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]      = id заявки (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 is_feasible(K: int) -> bool:
    req = 0  # указатель на следующую нерасписанную заявку
    # идём по дням 1..N
    for day in range(1, N + 1):
        used = 0
        # в день можно выполнить до K заявок, уже пришедших (arrivals[req] <= day)
        while used < K and req < M and arrivals[req] <= day:
            s = arrivals[req]
            if s + D < day:    # дедлайн прошёл
                return False
            req += 1
            used += 1
        # если следующая заявка ещё не пришла — простаиваем, это ок
        if req == M:
            return True
    return req == M

# --- печать расписания для найденного 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:
            # при минимальном валидном K дедлайны уже гарантированно не нарушаются
            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

# --- бинпоиск по числу машин ---
lo, hi = 1, M
while lo < hi:
    mid = (lo + hi) // 2
    if is_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 39%)

=======

• Subtask 1: 0 / 100