Submission #401926

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
401926	2021-05-11T02:29:18 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));
        PrintWriter outfile = new PrintWriter (System.out);
        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;
            }
        }
        outfile.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]){
                    outfile.print(j + " ");
                }
            }
            outfile.print("0");
            outfile.println();
        }
        outfile.close();
    }
    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

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	Incorrect	620 ms	21896 KB	Output isn't correct
2	Incorrect	636 ms	21876 KB	Output isn't correct
3	Incorrect	632 ms	21912 KB	Output isn't correct
4	Incorrect	611 ms	22252 KB	Output isn't correct
5	Incorrect	619 ms	22300 KB	Output isn't correct
6	Incorrect	616 ms	22404 KB	Output isn't correct
7	Incorrect	614 ms	22152 KB	Output isn't correct
8	Incorrect	617 ms	22476 KB	Output isn't correct
9	Execution timed out	1098 ms	21924 KB	Time limit exceeded
10	Execution timed out	1093 ms	21684 KB	Time limit exceeded
11	Execution timed out	1085 ms	21772 KB	Time limit exceeded
12	Execution timed out	1082 ms	29268 KB	Time limit exceeded
13	Execution timed out	1094 ms	40536 KB	Time limit exceeded
14	Execution timed out	1087 ms	47680 KB	Time limit exceeded
15	Execution timed out	1089 ms	51492 KB	Time limit exceeded
16	Execution timed out	1095 ms	57308 KB	Time limit exceeded
17	Runtime error	646 ms	65540 KB	Execution killed with signal 9
18	Runtime error	541 ms	65540 KB	Execution killed with signal 9
19	Runtime error	538 ms	65540 KB	Execution killed with signal 9
20	Runtime error	643 ms	65540 KB	Execution killed with signal 9