Submission #401916

#	Time	Username	Problem	Language	Result	Execution time	Memory
401916		rainliofficial	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1104 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 = 0;
        int high = n;
        while (low < high){
            int mid = (low + high)/2;
            if (check(mid, arr)){
                high = mid;
            }else{
                low = mid+1;
            }
        }

        ArrayList<Integer>[] eachDay = new ArrayList[n];
        for (int i=0; i<n; i++){
            eachDay[i] = new ArrayList<>();
        }

        int[] daycount = new int[low];
        for (int i=0; i<m; i++){
            eachDay[daycount[i%low]].add(arr[i][1]);
            daycount[i%low]++;
        }
        System.out.println(low);
        for (int i=0; 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;
        for (int i=0; i<m; i++){
            if (index == mid){
                index = 0;
            }
            if (end[index]+1 > arr[i][0]){
                if (end[index]-arr[i][0]+1 > d){
                    return false;
                }
                end[index]++;
            }else{
                end[index] = arr[i][0]; // No delay
            }
            index++;
        }
        return true;
    }
}

Compilation message (stderr)

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

• Subtask 1: 0 / 100