# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1083782 | NEMO_ | Job Scheduling (CEOI12_jobs) | Cpython 3 | 515 ms | 65536 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import heapq
from collections import defaultdict
def schedule_jobs(N, D, M, job_submissions):
job_queue = []
job_schedule = defaultdict(list)
max_machines = 0
submission_days = defaultdict(list)
# Organize job submissions by day
for i, day in enumerate(job_submissions, 1):
submission_days[day].append(i)
for day in range(1, N + 1):
# Add new job submissions to the priority queue
for job in submission_days[day]:
heapq.heappush(job_queue, (day + D, job))
# Process jobs for the current day
machines_used = 0
while job_queue and machines_used < len(job_queue):
deadline, job = heapq.heappop(job_queue)
if day <= deadline:
job_schedule[day].append(job)
machines_used += 1
else:
return None, None # Impossible to schedule within the delay constraint
max_machines = max(max_machines, machines_used)
return max_machines, job_schedule
def main():
# Read input
N, D, M = map(int, input().split())
job_submissions = list(map(int, input().split()))
# Schedule jobs
max_machines, schedule = schedule_jobs(N, D, M, job_submissions)
# Output results
if max_machines is None:
print("Impossible to schedule within the given delay constraint.")
else:
print(max_machines)
for day in range(1, N + 1):
print(*schedule[day], 0)
if __name__ == "__main__":
main()
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |