Submission #1281480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281480		osser	Job Scheduling (CEOI12_jobs)	Pypy 3	0 / 100	265 ms	131072 KiB

jobs

import sys
from array import array

# -------- быстрый ввод --------
data = sys.stdin.buffer.read().split()
it = iter(data)
def ni() -> int:
    return int(next(it))

N = ni()    # кол-во дней
D = ni()    # макс. задержка
M = ni()    # кол-во заявок

# дни подачи заявок S[0..M-1], гарантия: S[i] <= N - D
S = [ni() for _ in range(M)]

# -------- сформируем "плоский" порядок заявок, отсортированный по дню подачи --------
# cnt[d] = сколько заявок пришло в день d
cnt = [0] * (N + 2)
for s in S:
    cnt[s] += 1

# start[d] = начало блока заявок дня d в плоском массиве
start = [0] * (N + 2)
acc = 0
for d in range(1, N + 1):
    start[d] = acc
    acc += cnt[d]

# текущее место записи для каждого дня
cur = start[:]

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

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

=======

• Subtask 1: 0 / 100