oj.uz

Submission #517318

# Submission time Handle Problem Language Result Execution time Memory
517318 2022-01-23T03:22:50 Z perseverance201 Job Scheduling (CEOI12_jobs) Python 3
0 / 100
 1000 ms 65540 KB 
from pprint import pprint
n, d, m = list(map(int, input().strip().split()))
requests = list(map(int, input().strip().split()))
request_count = {}
for idx, request in enumerate(requests):
    if request in request_count:
        request_count[request].append(idx+1)
    else:
        request_count[request] = [idx+1]


def min_machine(x):
    pending_job = 0
    for day in range(1, n-d+1):
        pending_job += len(request_count.get(day, []))
        pending_job -= min(x, pending_job)
    if pending_job > 0:
        return False
    else:
        return True


def bin_search(low, high, f):
    while low < high:
        mid = low + (high-low)//2
        if f(mid):
            high = mid
        else:
            low = mid + 1
    return low

ans = bin_search(1, int(1e6), min_machine)
print(ans)
pending_job = []
ptr = 0
for day in range(1, n+1):
    pending_job += request_count.get(day, [])
    if ptr < len(pending_job):
        for i in range(ans):
            print(pending_job[ptr], end=' ')
            ptr += 1
        print(0)
    else:
        print(0)

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 280 ms 12700 KB Execution failed because the return code was nonzero
2 Runtime error 315 ms 12652 KB Execution failed because the return code was nonzero
3 Runtime error 266 ms 12664 KB Execution failed because the return code was nonzero
4 Runtime error 258 ms 12632 KB Execution failed because the return code was nonzero
5 Runtime error 248 ms 12656 KB Execution failed because the return code was nonzero
6 Runtime error 251 ms 12644 KB Execution failed because the return code was nonzero
7 Runtime error 256 ms 12736 KB Execution failed because the return code was nonzero
8 Runtime error 270 ms 12660 KB Execution failed because the return code was nonzero
9 Execution timed out 1058 ms 9300 KB Time limit exceeded
10 Execution timed out 1065 ms 10332 KB Time limit exceeded
11 Runtime error 121 ms 15300 KB Execution failed because the return code was nonzero
12 Runtime error 189 ms 26156 KB Execution failed because the return code was nonzero
13 Runtime error 270 ms 37672 KB Execution failed because the return code was nonzero
14 Runtime error 425 ms 50992 KB Execution failed because the return code was nonzero
15 Runtime error 408 ms 59680 KB Execution failed because the return code was nonzero
16 Runtime error 140 ms 65540 KB Execution killed with signal 9
17 Runtime error 110 ms 65536 KB Execution killed with signal 9
18 Runtime error 74 ms 65536 KB Execution killed with signal 9
19 Runtime error 87 ms 65540 KB Execution killed with signal 9
20 Runtime error 91 ms 65540 KB Execution killed with signal 9