Submission #401913

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
401913	2021-05-11T01:28:11 Z	rainliofficial	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	65540 KB

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++){
            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

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

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1093 ms	21792 KB	Time limit exceeded
2	Execution timed out	1105 ms	21704 KB	Time limit exceeded
3	Execution timed out	1091 ms	21644 KB	Time limit exceeded
4	Execution timed out	1096 ms	21648 KB	Time limit exceeded
5	Execution timed out	1080 ms	21700 KB	Time limit exceeded
6	Execution timed out	1092 ms	21764 KB	Time limit exceeded
7	Execution timed out	1050 ms	21712 KB	Time limit exceeded
8	Execution timed out	1067 ms	21652 KB	Time limit exceeded
9	Execution timed out	1096 ms	21500 KB	Time limit exceeded
10	Execution timed out	1085 ms	21776 KB	Time limit exceeded
11	Execution timed out	1090 ms	21468 KB	Time limit exceeded
12	Execution timed out	1061 ms	28936 KB	Time limit exceeded
13	Execution timed out	1096 ms	40124 KB	Time limit exceeded
14	Execution timed out	1089 ms	47192 KB	Time limit exceeded
15	Execution timed out	1097 ms	51496 KB	Time limit exceeded
16	Execution timed out	1091 ms	56844 KB	Time limit exceeded
17	Runtime error	663 ms	65540 KB	Execution killed with signal 9
18	Runtime error	538 ms	65540 KB	Execution killed with signal 9
19	Runtime error	555 ms	65536 KB	Execution killed with signal 9
20	Runtime error	658 ms	65536 KB	Execution killed with signal 9