Submission #1119495

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119495	2024-11-27T05:24:49 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	50 / 100	1000 ms	26552 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 + 1];
        int[] sc = new int[m + 1];
        for (int i = 1; i <= m; i++) {
            fr[i] = reader.nextInt();
            sc[i] = i;
        }

        // Sort `fr` and rearrange `sc` accordingly
        quickSort(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 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();
    }

    // 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	1052 ms	13952 KB	Time limit exceeded
2	Execution timed out	1057 ms	13688 KB	Time limit exceeded
3	Execution timed out	1059 ms	13440 KB	Time limit exceeded
4	Execution timed out	1035 ms	13444 KB	Time limit exceeded
5	Execution timed out	1054 ms	13412 KB	Time limit exceeded
6	Execution timed out	1052 ms	13388 KB	Time limit exceeded
7	Execution timed out	1068 ms	13416 KB	Time limit exceeded
8	Execution timed out	1063 ms	13936 KB	Time limit exceeded
9	Correct	861 ms	16544 KB	Output is correct
10	Correct	662 ms	16328 KB	Output is correct
11	Correct	262 ms	14908 KB	Output is correct
12	Correct	368 ms	17556 KB	Output is correct
13	Correct	379 ms	18356 KB	Output is correct
14	Correct	345 ms	19864 KB	Output is correct
15	Correct	705 ms	22232 KB	Output is correct
16	Correct	362 ms	23168 KB	Output is correct
17	Correct	443 ms	26552 KB	Output is correct
18	Execution timed out	1040 ms	18924 KB	Time limit exceeded
19	Execution timed out	1050 ms	19036 KB	Time limit exceeded
20	Correct	423 ms	26192 KB	Output is correct