Submission #875573

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
875573	2023-11-20T04:33:09 Z	rajat	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	115 ms	30104 KB

jobs

import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new FileReader("in.txt"));
        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	101 ms	30040 KB	Execution failed because the return code was nonzero
2	Runtime error	102 ms	25716 KB	Execution failed because the return code was nonzero
3	Runtime error	101 ms	25584 KB	Execution failed because the return code was nonzero
4	Runtime error	102 ms	27688 KB	Execution failed because the return code was nonzero
5	Runtime error	103 ms	25284 KB	Execution failed because the return code was nonzero
6	Runtime error	101 ms	25472 KB	Execution failed because the return code was nonzero
7	Runtime error	101 ms	26068 KB	Execution failed because the return code was nonzero
8	Runtime error	101 ms	27176 KB	Execution failed because the return code was nonzero
9	Runtime error	101 ms	25504 KB	Execution failed because the return code was nonzero
10	Runtime error	100 ms	25844 KB	Execution failed because the return code was nonzero
11	Runtime error	102 ms	25628 KB	Execution failed because the return code was nonzero
12	Runtime error	103 ms	29288 KB	Execution failed because the return code was nonzero
13	Runtime error	103 ms	30104 KB	Execution failed because the return code was nonzero
14	Runtime error	101 ms	25428 KB	Execution failed because the return code was nonzero
15	Runtime error	102 ms	25696 KB	Execution failed because the return code was nonzero
16	Runtime error	115 ms	25140 KB	Execution failed because the return code was nonzero
17	Runtime error	101 ms	26012 KB	Execution failed because the return code was nonzero
18	Runtime error	102 ms	25452 KB	Execution failed because the return code was nonzero
19	Runtime error	104 ms	29632 KB	Execution failed because the return code was nonzero
20	Runtime error	101 ms	25304 KB	Execution failed because the return code was nonzero