Submission #875572

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
875572	2023-11-20T04:29:24 Z	rajat	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	115 ms	29992 KB

jobs

import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        Val[] arr = new Val[m];
        HashMap<Integer, Integer> switchArr = new HashMap<>();
        for (int i = 0; i < m; i++) {
            int num = Integer.parseInt(st.nextToken());
            arr[i] = new Val(num, i + 1);
        }
        Arrays.sort(arr, Comparator.comparingInt(s -> s.num));
        int curValue = 1;
        for (int i = 1; i < m; i++) {
            if (arr[i] != arr[i - 1]) {
                switchArr.put(curValue, i);
                curValue = arr[i].num;
            }
        }
        switchArr.put(arr[m - 1].num, m);
        int low = 1;
        int high = m;
        while (low <= high) {
            int mid = (low + high + 1)/2;
            if (works(mid, n, arr, d, switchArr)) {
                high = mid - 1;
            }
            else {
                low = mid + 1;
            }
        }
        StringBuilder str = new StringBuilder();
        str.append(low);
        int arrInd = 0;
        for (int i = 1; i <= n; i++) {
            if (arrInd >= arr.length || arr[arrInd].num > i ) {
                str.append("\n");
                str.append(0);
                continue;
            }
            int prevStart = arrInd;
            int posCurJob = arrInd + low;
            arrInd = posCurJob;
            if (switchArr.containsKey(i)) {
                arrInd = Math.min(posCurJob, switchArr.get(i));
            }
            int end = Math.min(m, arrInd);
            str.append("\n");
            for (int j = prevStart; j < end; j++) {
                str.append(arr[j].ind + " ");
            }
            str.append(0);
        }
        System.out.println(str);
        br.close();
    }

    public static boolean works(int mid, int n, Val[] arr, int d, HashMap<Integer, Integer> switchArr) {
        int arrInd = 0;
        for (int i = 1; i <= n; i++) {
            int curJob = arr[arrInd].num;
            if (curJob > i) {
                continue;
            }
            if (curJob + d < i) {
                return false;
            }
            int posCurJob = arrInd + mid;
            arrInd = posCurJob;
            if (switchArr.containsKey(i)) {
                arrInd = Math.min(posCurJob, switchArr.get(i));
            }
            if (arrInd >= arr.length) {
                return true;
            }
        }
        return arrInd >= arr.length;
    }

    static class Val {
        int num, ind;
        public Val(int num, int ind) {
            this.num = num;
            this.ind = ind;
        }
    }
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	102 ms	26092 KB	Execution failed because the return code was nonzero
2	Runtime error	110 ms	25188 KB	Execution failed because the return code was nonzero
3	Runtime error	103 ms	29808 KB	Execution failed because the return code was nonzero
4	Runtime error	102 ms	29300 KB	Execution failed because the return code was nonzero
5	Runtime error	101 ms	25640 KB	Execution failed because the return code was nonzero
6	Runtime error	100 ms	27644 KB	Execution failed because the return code was nonzero
7	Runtime error	101 ms	25456 KB	Execution failed because the return code was nonzero
8	Runtime error	115 ms	25660 KB	Execution failed because the return code was nonzero
9	Runtime error	101 ms	25840 KB	Execution failed because the return code was nonzero
10	Runtime error	102 ms	29436 KB	Execution failed because the return code was nonzero
11	Runtime error	103 ms	29536 KB	Execution failed because the return code was nonzero
12	Runtime error	109 ms	25732 KB	Execution failed because the return code was nonzero
13	Runtime error	101 ms	29992 KB	Execution failed because the return code was nonzero
14	Runtime error	102 ms	29568 KB	Execution failed because the return code was nonzero
15	Runtime error	103 ms	25700 KB	Execution failed because the return code was nonzero
16	Runtime error	113 ms	25164 KB	Execution failed because the return code was nonzero
17	Runtime error	100 ms	26224 KB	Execution failed because the return code was nonzero
18	Runtime error	101 ms	29784 KB	Execution failed because the return code was nonzero
19	Runtime error	102 ms	25720 KB	Execution failed because the return code was nonzero
20	Runtime error	106 ms	26180 KB	Execution failed because the return code was nonzero