Submission #401925

#	Time	Username	Problem	Language	Result	Execution time	Memory
401925		rainliofficial	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1103 ms	65540 KiB

jobs

import java.io.*;
import java.util.*;

public class jobs { 
    static int n, d, m;
    public static void main(String[] args) throws IOException{
        BufferedReader file = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(file.readLine());
        n = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        int[][] arr = new int[m][2];
        st = new StringTokenizer(file.readLine());
        for (int i=0; i<m; i++){
            arr[i] = new int[] {Integer.parseInt(st.nextToken()), i+1};
        }
        Arrays.sort(arr, (a, b) -> a[0]-b[0]);
        int low = 1;
        int high = 10000;
        while (low < high){
            int mid = (low + high)/2;
            if (check(mid, arr)){
                high = mid;
            }else{
                low = mid+1;
            }
        }
        System.out.println(low);
        ArrayList<Integer>[] eachDay = new ArrayList[n+1];
        for (int i=0; i<=n; i++){
            eachDay[i] = new ArrayList<>();
        }
        int[] end = new int[low];
        for (int i=0, id = 0; i<m; i++, id++){
            if (id == low){
                id = 0;
            }
            int requestDay = arr[i][0];
            int canDo = end[id]+1;
            end[id] = Math.max(requestDay, canDo); // Only does work when the request comes
            eachDay[end[id]].add(arr[i][1]);
        }
        for (int i=1; i<=n; i++){
            if (eachDay[i] != null){
                for (int j : eachDay[i]){
                    System.out.print(j + " ");
                }
            }
            System.out.print("0");
            System.out.println();
        }
    }
    public static boolean check(int mid, int[][] arr){
        int[] end = new int[mid]; // Tracks when a machine ends its job
        int index = 0;
        int maxD = 0;
        for (int i=0; i<m; i++){
            if (index == mid){
                index = 0;
            }
            if (end[index]+1 > arr[i][0]){
                maxD = Math.max(maxD, end[index]+1-arr[i][0]);
                end[index]++;
            }else{
                end[index] = arr[i][0]; // No delay
            }
            index++;
        }
        return maxD <= d;
    }
}

Compilation message (stderr)

Note: jobs.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

• Subtask 1: 0 / 100