Submission #1104968

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1104968	2024-10-25T02:43:07 Z	APerson	Job Scheduling (CEOI12_jobs)	Java 11	5 / 100	1000 ms	65432 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++;
            lastUsed[index] = day;
            if(curDay - lastUsed[index] > d) return false;
            index++;
        }
        return true;
    }
}

Subtask #1

5.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1000 ms	27692 KB	Time limit exceeded
2	Incorrect	966 ms	27228 KB	Output isn't correct
3	Incorrect	967 ms	27380 KB	Output isn't correct
4	Execution timed out	1033 ms	26964 KB	Time limit exceeded
5	Execution timed out	1016 ms	27372 KB	Time limit exceeded
6	Execution timed out	1065 ms	27008 KB	Time limit exceeded
7	Execution timed out	1065 ms	26964 KB	Time limit exceeded
8	Execution timed out	1060 ms	26940 KB	Time limit exceeded
9	Execution timed out	1057 ms	30108 KB	Time limit exceeded
10	Execution timed out	1054 ms	30632 KB	Time limit exceeded
11	Correct	964 ms	29308 KB	Output is correct
12	Execution timed out	1065 ms	37696 KB	Time limit exceeded
13	Execution timed out	1055 ms	45912 KB	Time limit exceeded
14	Execution timed out	1043 ms	48408 KB	Time limit exceeded
15	Execution timed out	1066 ms	51684 KB	Time limit exceeded
16	Execution timed out	1068 ms	63968 KB	Time limit exceeded
17	Execution timed out	1053 ms	48032 KB	Time limit exceeded
18	Execution timed out	1057 ms	65432 KB	Time limit exceeded
19	Execution timed out	1056 ms	60148 KB	Time limit exceeded
20	Execution timed out	1070 ms	51844 KB	Time limit exceeded