Submission #1119494

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119494	2024-11-27T05:23:46 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	117 ms	18372 KB

jobs

import java.io.*;
import java.util.*;

public class jobs {
    public static void main(String[] args) throws IOException {
        FastInputReader reader = new FastInputReader(System.in);

        int n = reader.nextInt(); // Number of days
        int d = reader.nextInt(); // Delay allowed
        int m = reader.nextInt(); // Number of events

        // Use separate arrays for efficiency
        int[] fr = new int[m + 2];
        int[] sc = new int[m + 2];
        for (int i = 1; i <= m; i++) {
            fr[i] = reader.nextInt();
            sc[i] = i;
        }
        // Add a dummy event at the end
        fr[m + 1] = Integer.MAX_VALUE;

        // Sort `fr` and rearrange `sc` accordingly
        sortWithIndex(fr, sc, 1, m);

        int l = 0, r = m;

        while (r - l > 1) {
            int mid = (l + r) / 2;
            int p = 1;

            for (int i = 1; i <= n; i++) {
                if (p > m || fr[p] + d < i) {
                    break;
                }
                int cnt = 0;
                while (cnt < mid && p <= m && fr[p] <= i) {
                    cnt++;
                    p++;
                }
            }

            if (p > m) {
                r = mid;
            } else {
                l = mid;
            }
        }

        // Output the result
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(r + "\n");

        int p = 1;
        for (int i = 1; i <= n; i++) {
            int cnt = 0;
            while (cnt < r && p <= m && fr[p] <= i) {
                bw.write(sc[p] + " ");
                cnt++;
                p++;
            }
            bw.write("0\n");
        }
        bw.flush();
    }

    // Sort arrays `fr` and `sc` together
    private static void sortWithIndex(int[] fr, int[] sc, int low, int high) {
        Arrays.sort(new int[][] { fr, sc }, low, high + 1, Comparator.comparingInt(a -> a[0]));
    }

    static class FastInputReader {
        private final DataInputStream din;
        private final byte[] buffer;
        private int bufferPointer, bytesRead;

        public FastInputReader(InputStream in) {
            din = new DataInputStream(in);
            buffer = new byte[1 << 16]; // 64 KB buffer
            bufferPointer = bytesRead = 0;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead) {
                bytesRead = din.read(buffer, 0, buffer.length);
                bufferPointer = 0;
                if (bytesRead == -1) return -1; // End of stream
            }
            return buffer[bufferPointer++];
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') c = read(); // Skip whitespace
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg) return -ret;
            return ret;
        }
    }
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	94 ms	11244 KB	Execution failed because the return code was nonzero
2	Runtime error	85 ms	10868 KB	Execution failed because the return code was nonzero
3	Runtime error	85 ms	11536 KB	Execution failed because the return code was nonzero
4	Runtime error	88 ms	11208 KB	Execution failed because the return code was nonzero
5	Runtime error	97 ms	10868 KB	Execution failed because the return code was nonzero
6	Runtime error	87 ms	11548 KB	Execution failed because the return code was nonzero
7	Runtime error	86 ms	10840 KB	Execution failed because the return code was nonzero
8	Runtime error	86 ms	10740 KB	Execution failed because the return code was nonzero
9	Runtime error	85 ms	11248 KB	Execution failed because the return code was nonzero
10	Runtime error	85 ms	11732 KB	Execution failed because the return code was nonzero
11	Runtime error	83 ms	10876 KB	Execution failed because the return code was nonzero
12	Runtime error	87 ms	12556 KB	Execution failed because the return code was nonzero
13	Runtime error	100 ms	13032 KB	Execution failed because the return code was nonzero
14	Runtime error	95 ms	13736 KB	Execution failed because the return code was nonzero
15	Runtime error	94 ms	14144 KB	Execution failed because the return code was nonzero
16	Runtime error	90 ms	15224 KB	Execution failed because the return code was nonzero
17	Runtime error	97 ms	15824 KB	Execution failed because the return code was nonzero
18	Runtime error	103 ms	18372 KB	Execution failed because the return code was nonzero
19	Runtime error	117 ms	18284 KB	Execution failed because the return code was nonzero
20	Runtime error	94 ms	16312 KB	Execution failed because the return code was nonzero