Submission #517319

# Submission time Handle Problem Language Result Execution time Memory
517319 2022-01-23T03:25:16 Z perseverance201 Job Scheduling (CEOI12_jobs) Python 3
0 / 100
1000 ms 65540 KB
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)
# Verdict Execution time Memory Grader output
1 Runtime error 223 ms 11080 KB Execution failed because the return code was nonzero
2 Runtime error 236 ms 11060 KB Execution failed because the return code was nonzero
3 Runtime error 248 ms 11108 KB Execution failed because the return code was nonzero
4 Runtime error 223 ms 11228 KB Execution failed because the return code was nonzero
5 Runtime error 233 ms 11112 KB Execution failed because the return code was nonzero
6 Runtime error 224 ms 11060 KB Execution failed because the return code was nonzero
7 Runtime error 244 ms 11120 KB Execution failed because the return code was nonzero
8 Runtime error 235 ms 11076 KB Execution failed because the return code was nonzero
9 Execution timed out 1025 ms 10732 KB Time limit exceeded
10 Execution timed out 1066 ms 9508 KB Time limit exceeded
11 Runtime error 90 ms 13436 KB Execution failed because the return code was nonzero
12 Runtime error 159 ms 23892 KB Execution failed because the return code was nonzero
13 Runtime error 215 ms 35244 KB Execution failed because the return code was nonzero
14 Runtime error 423 ms 50276 KB Execution failed because the return code was nonzero
15 Runtime error 358 ms 57216 KB Execution failed because the return code was nonzero
16 Runtime error 114 ms 65540 KB Execution killed with signal 9
17 Runtime error 115 ms 65540 KB Execution killed with signal 9
18 Runtime error 67 ms 65536 KB Execution killed with signal 9
19 Runtime error 69 ms 65536 KB Execution killed with signal 9
20 Runtime error 98 ms 65540 KB Execution killed with signal 9