Submission #1281475

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

jobs

import sys

def main():
    input = sys.stdin.readline

    N, D, M = map(int, input().split())
    S = list(map(int, input().split()))
    # jobs: (arrival_day, id)
    jobs = [(S[i], i + 1) for i in range(M)]
    jobs.sort()  # sort by arrival day (also deadline order)

    # Feasibility check for given K; if build=True, also returns a schedule
    def simulate(K: int, build: bool = False):
        req = 0  # pointer to next unscheduled job in "jobs"
        schedule = [[] for _ in range(N)] if build else None

        # Simulate days 1..N
        for day in range(1, N + 1):
            used = 0
            # Try to schedule up to K jobs today, in arrival order,
            # but only those that have arrived (jobs[req][0] <= day).
            while used < K and req < M and jobs[req][0] <= day:
                s, jid = jobs[req]
                # If this job's deadline already passed, infeasible
                if s + D < day:
                    return False, None
                if build:
                    schedule[day - 1].append(jid)
                req += 1
                used += 1

            # (If the next job hasn't arrived yet, we just leave machines idle today.)

        # After day N, all jobs must be scheduled
        if req == M:
            return True, schedule
        return False, None

    # Binary search the minimal K
    lo, hi = 1, M
    best_sched = None
    while lo < hi:
        mid = (lo + hi) // 2
        ok, _ = simulate(mid, build=False)
        if ok:
            hi = mid
        else:
            lo = mid + 1

    # Build schedule for minimal K
    _, best_sched = simulate(lo, build=True)

    # Output
    print(lo)
    for day in range(N):
        if best_sched[day]:
            print(*best_sched[day], 0)
        else:
            print(0)

if __name__ == "__main__":
    main()

Compilation message (stdout)

Compiling 'jobs.py'...

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

=======

• Subtask 1: 0 / 100