Submission #659419

#	Time	Username	Problem	Language	Result	Execution time	Memory
659419		pizet	Job Scheduling (CEOI12_jobs)	Pypy 3	0 / 100	1089 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 discrete_binary_search(func, lo, hi):
        """ Locate the first value x s.t. func(x) = True within [lo, hi] """
        while lo < hi:
            mi = lo + (hi - lo) // 2
            if func(mi):
                hi = mi
            else:
                lo = mi + 1

        return lo

    ans = discrete_binary_search(cond, 1, m)
    print(ans)
    j = 0
    for i in range(1, n+1):
        curr = 0
        while j < m and curr < ans and jobs[j][0] <= i:
            print(jobs[j][1], end=' ')
            curr += 1
            j += 1
        print(0)


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

if __name__ == '__main__':
    main()

• Subtask 1: 0 / 100