Submission #401899

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

jobs

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

public class jobs { 
    static int n, d, m;
    static ArrayList<Integer>[] out;
    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;
            }
        }
        System.out.println(low);
        for (int i=0; i<n; i++){
            for (int j : out[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;
        out = new ArrayList[n];
        for (int i=0; i<n; i++){
            out[i] = new ArrayList<>();
        }
        for (int i=0; i<m; i++){
            if (index == mid){
                index = 0;
            }
            if (end[index]-arr[i][0]+1 > d){
                return false;
            }
            end[index]++;
            out[end[index]].add(arr[i][1]);
            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