Submission #1119486

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119486	2024-11-27T05:17:00 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	60 / 100	1000 ms	51916 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 a single array to store both `fr` and `sc` values
        Pair[] a = new Pair[m + 1];
        for (int i = 1; i <= m; i++) {
            a[i] = new Pair(reader.nextInt(), i);
        }

        // Sort using Arrays.sort for simplicity
        Arrays.sort(a, 1, m + 1);

        int l = 0, r = m;

        // Binary search for the minimum value of `r`
        while (r - l > 1) {
            int mid = (l + r) / 2;
            int p = 1;

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

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

        // Output results
        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 && a[p].fr <= i) {
                bw.write(a[p].sc + " ");
                cnt++;
                p++;
            }
            bw.write("0\n");
        }
        bw.flush();
    }

    static class Pair implements Comparable<Pair> {
        int fr, sc;

        Pair(int fr, int sc) {
            this.fr = fr;
            this.sc = sc;
        }

        @Override
        public int compareTo(Pair other) {
            return Integer.compare(this.fr, other.fr);
        }
    }

    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

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	254 ms	19184 KB	Output is correct
2	Correct	244 ms	18936 KB	Output is correct
3	Correct	253 ms	19240 KB	Output is correct
4	Correct	280 ms	19324 KB	Output is correct
5	Correct	271 ms	19120 KB	Output is correct
6	Correct	257 ms	19048 KB	Output is correct
7	Correct	257 ms	19072 KB	Output is correct
8	Correct	270 ms	19324 KB	Output is correct
9	Correct	738 ms	20996 KB	Output is correct
10	Correct	789 ms	20976 KB	Output is correct
11	Correct	793 ms	21012 KB	Output is correct
12	Correct	947 ms	26432 KB	Output is correct
13	Execution timed out	1035 ms	27528 KB	Time limit exceeded
14	Runtime error	975 ms	38608 KB	Memory limit exceeded
15	Execution timed out	1055 ms	35640 KB	Time limit exceeded
16	Execution timed out	1060 ms	36616 KB	Time limit exceeded
17	Execution timed out	1053 ms	39596 KB	Time limit exceeded
18	Execution timed out	1055 ms	41044 KB	Time limit exceeded
19	Execution timed out	1074 ms	51916 KB	Time limit exceeded
20	Execution timed out	1056 ms	41060 KB	Time limit exceeded