Submission #659432

#	Time	Username	Problem	Language	Result	Execution time	Memory
659432		pizet	Job Scheduling (CEOI12_jobs)	Pypy 3	0 / 100	1094 ms	65536 KiB

jobs

#!/usr/bin/env python3

import math
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

def test_case():
    n, d, m = map(int, input().split())
    jobs = []
    cnt = [0 for _ in range(n+1)]
    i = 1
    for x in input().split():
        jobs.append([int(x), i])
        cnt[jobs[-1][0]] += 1
        i += 1
    jobs.sort()
#    print(jobs)

    def cond(x):
        max_d = 0
        j = 0
        for i in range(1, n+1):
            curr = 0
            while j < m and curr < x and jobs[j][0] <= i:
#                print(i, jobs[j])
                max_d = max(max_d, i-jobs[j][0])
                if max_d > d: return False
                curr += 1
                j += 1
#        print(x, max_d)
#        print("=======")
        return True

    def cond2(x):
        req_num = 0
        schedule = [[] for _ in range(n)]
        for day in range(1, n+1):
            for j in range(x):
                if jobs[req_num][0] > day:
                    break
                if jobs[req_num][0] + d >= day:
                    schedule[day-1].append(jobs[req_num][1])
                    req_num += 1
                else:
                    return False, schedule
                if req_num == m:
                    return True, schedule
        return False, schedule



    def discrete_binary_search(func, lo, hi):
        """ Locate the first value x s.t. func(x) = True within [lo, hi] """
        res = []
        while lo < hi:
            mi = lo + (hi - lo) // 2
            res1, res2 = func(mi)
            if res1:
                hi = mi
                res = res2
            else:
                lo = mi + 1

        return lo, res

    ans, res = discrete_binary_search(cond2, 1, m)
    print(ans)
    for i in range(n):
        if len(res[i]) > 0:
            print(*res[i], end=' ')
            print(0)
        else:
            print(0)

def main():
    t = 1
#    t = int(input())
    for _ in range(t):
        test_case()

if __name__ == '__main__':
    main()

• Subtask 1: 0 / 100