Submission #1119484

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

        // Separate arrays for `fr` and `sc`
        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 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
        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();
    }

    // Custom 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	1055 ms	17864 KB	Time limit exceeded
2	Execution timed out	1050 ms	17564 KB	Time limit exceeded
3	Execution timed out	1066 ms	15520 KB	Time limit exceeded
4	Execution timed out	1051 ms	17864 KB	Time limit exceeded
5	Execution timed out	1057 ms	15844 KB	Time limit exceeded
6	Execution timed out	1053 ms	17508 KB	Time limit exceeded
7	Execution timed out	1057 ms	17896 KB	Time limit exceeded
8	Execution timed out	1042 ms	15224 KB	Time limit exceeded
9	Correct	973 ms	20048 KB	Output is correct
10	Correct	733 ms	19652 KB	Output is correct
11	Correct	281 ms	18740 KB	Output is correct
12	Correct	355 ms	18992 KB	Output is correct
13	Correct	371 ms	19948 KB	Output is correct
14	Correct	334 ms	23100 KB	Output is correct
15	Correct	683 ms	23172 KB	Output is correct
16	Correct	380 ms	24108 KB	Output is correct
17	Correct	429 ms	29876 KB	Output is correct
18	Execution timed out	1070 ms	23128 KB	Time limit exceeded
19	Execution timed out	1060 ms	22072 KB	Time limit exceeded
20	Correct	446 ms	29624 KB	Output is correct