Submission #1119487

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119487	2024-11-27T05:18:22 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	50 / 100	1000 ms	26160 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 `fr` and `sc` to save memory and improve speed
        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` and rearrange `sc` using in-place quicksort
        quickSort(fr, sc, 1, m);

        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 || 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 for efficiency
        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();
    }

    // Optimized quicksort to sort `fr` and rearrange `sc` accordingly
    private static void quickSort(int[] fr, int[] sc, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(fr, sc, low, high);
            quickSort(fr, sc, low, pivotIndex - 1);
            quickSort(fr, sc, pivotIndex + 1, high);
        }
    }

    private static int partition(int[] fr, int[] sc, int low, int high) {
        int pivot = fr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (fr[j] <= pivot) {
                i++;
                swap(fr, sc, i, j);
            }
        }
        swap(fr, sc, i + 1, high);
        return i + 1;
    }

    private static void swap(int[] fr, int[] sc, int i, int j) {
        int tempFr = fr[i];
        fr[i] = fr[j];
        fr[j] = tempFr;

        int tempSc = sc[i];
        sc[i] = sc[j];
        sc[j] = tempSc;
    }

    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	Execution timed out	1053 ms	13432 KB	Time limit exceeded
2	Execution timed out	1069 ms	13832 KB	Time limit exceeded
3	Execution timed out	1055 ms	13896 KB	Time limit exceeded
4	Execution timed out	1057 ms	13840 KB	Time limit exceeded
5	Execution timed out	1067 ms	13884 KB	Time limit exceeded
6	Execution timed out	1044 ms	13704 KB	Time limit exceeded
7	Execution timed out	1076 ms	13704 KB	Time limit exceeded
8	Execution timed out	1059 ms	13180 KB	Time limit exceeded
9	Correct	993 ms	16560 KB	Output is correct
10	Correct	800 ms	16156 KB	Output is correct
11	Correct	288 ms	15008 KB	Output is correct
12	Correct	362 ms	17496 KB	Output is correct
13	Correct	402 ms	18232 KB	Output is correct
14	Correct	326 ms	19680 KB	Output is correct
15	Correct	692 ms	22120 KB	Output is correct
16	Correct	421 ms	22612 KB	Output is correct
17	Correct	494 ms	26160 KB	Output is correct
18	Execution timed out	1047 ms	19676 KB	Time limit exceeded
19	Execution timed out	1049 ms	19116 KB	Time limit exceeded
20	Correct	477 ms	26056 KB	Output is correct