Submission #1105200

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1105200	2024-10-25T17:31:55 Z	APerson	Job Scheduling (CEOI12_jobs)	Java 11	15 / 100	1000 ms	65536 KB

jobs

import java.util.*;
public class jobs {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int d = sc.nextInt();
        int m = sc.nextInt();
        ArrayList<ArrayList<Integer>> days = new ArrayList<>();
        for(int i = 0; i < n; i++) days.add(new ArrayList<>());
        for(int i = 1; i <= m; i++) {
            days.get(sc.nextInt()).add(i);
        }

        // turn input into a list where they are all just the days of the jobs
        ArrayList<Integer> jobs = new ArrayList<>();
        ArrayList<Integer> forPrinting = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            forPrinting.addAll(days.get(i));
            for(int j = 0; j < days.get(i).size(); j++) {
                jobs.add(i);
            }
        }
        Collections.reverse(forPrinting);

        // binary search on answer
        int min = 1;
        int max = m;
        while(min != max) {
            int mid = (min + max)/2;
            if(works(mid, d, jobs)) {
                max = mid;
            } else {
                min = mid + 1;
            }
        }

        // output answer
        System.out.println(min);
        for(int i = 0; i < n; i++) {
            int index = min;
            while(index > 0 && !forPrinting.isEmpty()) {
                System.out.print(forPrinting.remove(forPrinting.size() - 1) + " ");
                index--;
            }
            System.out.println(0);
        }
        sc.close();
    }
    public static boolean works(int mid, int d, ArrayList<Integer> days) {
        int[] lastUsed = new int[mid];
        int index = 0;
        int curDay = 0;
        for (int day : days) {
            index %= mid;
            if(index == 0) curDay++;
            if(day > curDay) {
                curDay = day;
                index = 0;
            }
            lastUsed[index] = day;
            if(curDay - day > d) return false;
            index++;
        }
        return true;
    }
}

Subtask #1

15.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	992 ms	27460 KB	Output is correct
2	Correct	987 ms	27436 KB	Output is correct
3	Execution timed out	1057 ms	26976 KB	Time limit exceeded
4	Execution timed out	1046 ms	26908 KB	Time limit exceeded
5	Execution timed out	1073 ms	27072 KB	Time limit exceeded
6	Execution timed out	1042 ms	27292 KB	Time limit exceeded
7	Execution timed out	1022 ms	27204 KB	Time limit exceeded
8	Execution timed out	1016 ms	27252 KB	Time limit exceeded
9	Execution timed out	1058 ms	30192 KB	Time limit exceeded
10	Execution timed out	1036 ms	30660 KB	Time limit exceeded
11	Correct	965 ms	29488 KB	Output is correct
12	Execution timed out	1053 ms	37384 KB	Time limit exceeded
13	Execution timed out	1071 ms	45732 KB	Time limit exceeded
14	Execution timed out	1073 ms	50404 KB	Time limit exceeded
15	Execution timed out	1055 ms	51408 KB	Time limit exceeded
16	Execution timed out	1052 ms	63728 KB	Time limit exceeded
17	Execution timed out	1060 ms	51932 KB	Time limit exceeded
18	Execution timed out	1043 ms	65536 KB	Time limit exceeded
19	Execution timed out	1074 ms	65536 KB	Time limit exceeded
20	Execution timed out	1046 ms	65536 KB	Time limit exceeded