Submission #435057

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
435057	2021-06-22T21:47:00 Z	mnair797	Job Scheduling (CEOI12_jobs)	Java 11	40 / 100	1000 ms	65540 KB

jobs

import java.io.*;
import java.util.*;
 
public class jobs { 
    static int n;
    static int d;
    static int m;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter (System.out);
        StringTokenizer st = new StringTokenizer(br.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(br.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 = m;
        while (low < high){
            int mid = (low + high)/2;
            if (check(mid, arr)){
                high = mid;
            }else{
                low = mid+1;
            }
        }
        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); 
            eachDay[end[id]].add(arr[i][1]);
        }
        for (int i=1; i<=n; i++){
            if (eachDay[i] != null){
                for (int j : eachDay[i]){
                	out.print(j + " ");
                }
            }
            out.print("0");
            out.println();
        }
        out.close();
    }
    public static boolean check(int mid, int[][] arr){
        int[] end = new int[mid]; 
        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]; 
            }
            index++;
        }
        return maxD <= d;
    }
}

Compilation message

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

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	678 ms	22984 KB	Output is correct
2	Correct	722 ms	22328 KB	Output is correct
3	Correct	684 ms	22360 KB	Output is correct
4	Correct	682 ms	22264 KB	Output is correct
5	Correct	737 ms	22148 KB	Output is correct
6	Correct	682 ms	22264 KB	Output is correct
7	Correct	701 ms	22124 KB	Output is correct
8	Correct	746 ms	22296 KB	Output is correct
9	Execution timed out	1096 ms	21564 KB	Time limit exceeded
10	Execution timed out	1075 ms	21760 KB	Time limit exceeded
11	Execution timed out	1077 ms	22024 KB	Time limit exceeded
12	Execution timed out	1079 ms	29580 KB	Time limit exceeded
13	Execution timed out	1069 ms	41304 KB	Time limit exceeded
14	Execution timed out	1094 ms	48820 KB	Time limit exceeded
15	Execution timed out	1089 ms	53216 KB	Time limit exceeded
16	Execution timed out	1087 ms	59604 KB	Time limit exceeded
17	Runtime error	654 ms	65536 KB	Execution killed with signal 9
18	Runtime error	583 ms	65540 KB	Execution killed with signal 9
19	Runtime error	566 ms	65536 KB	Execution killed with signal 9
20	Runtime error	643 ms	65540 KB	Execution killed with signal 9