Submission #1119492

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119492	2024-11-27T05:22:22 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	50 / 100	1000 ms	52924 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

        // Dynamically decide based on the size of `n` and `m`
        if (n * m <= 10000) {
            // Use simple logic for small inputs
            simpleSmallCaseApproach(reader, n, d, m);
        } else {
            // Use optimized logic for larger inputs
            optimizedLargeCaseApproach(reader, n, d, m);
        }
    }

    // Handle small cases with a simple approach
    private static void simpleSmallCaseApproach(FastInputReader reader, int n, int d, int m) throws IOException {
        Pair[] a = new Pair[m + 1];
        for (int i = 1; i <= m; i++) {
            a[i] = new Pair(reader.nextInt(), i);
        }

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

        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 || 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 using BufferedWriter
        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();
    }

    // Handle large cases with an optimized approach
    private static void optimizedLargeCaseApproach(FastInputReader reader, int n, int d, int m) throws IOException {
        int[] fr = new int[m + 1];
        int[] sc = new int[m + 1];
        for (int i = 1; i <= m; i++) {
            fr[i] = reader.nextInt();
            sc[i] = i;
        }

        // Sort by `fr` using Arrays.sort
        Arrays.sort(fr, 1, m + 1);

        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 results using BufferedWriter
        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();
    }

    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

50.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	223 ms	20828 KB	Output is correct
2	Correct	257 ms	16712 KB	Output is correct
3	Correct	241 ms	20608 KB	Output is correct
4	Correct	256 ms	15588 KB	Output is correct
5	Correct	265 ms	19056 KB	Output is correct
6	Correct	255 ms	20636 KB	Output is correct
7	Correct	264 ms	20528 KB	Output is correct
8	Correct	260 ms	18828 KB	Output is correct
9	Partially correct	329 ms	26824 KB	Partially correct
10	Partially correct	403 ms	27176 KB	Partially correct
11	Partially correct	413 ms	27468 KB	Partially correct
12	Partially correct	400 ms	29816 KB	Partially correct
13	Partially correct	443 ms	31956 KB	Partially correct
14	Execution timed out	1078 ms	36516 KB	Time limit exceeded
15	Runtime error	441 ms	35832 KB	Memory limit exceeded
16	Runtime error	492 ms	36668 KB	Memory limit exceeded
17	Execution timed out	1064 ms	41184 KB	Time limit exceeded
18	Execution timed out	1065 ms	39380 KB	Time limit exceeded
19	Execution timed out	1066 ms	52924 KB	Time limit exceeded
20	Execution timed out	1046 ms	39544 KB	Time limit exceeded