Submission #1119506

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119506	2024-11-27T05:43:04 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	50 / 100	1000 ms	26152 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	1038 ms	13452 KB	Time limit exceeded
2	Execution timed out	1061 ms	13996 KB	Time limit exceeded
3	Execution timed out	1071 ms	13812 KB	Time limit exceeded
4	Execution timed out	1071 ms	13628 KB	Time limit exceeded
5	Execution timed out	1065 ms	13656 KB	Time limit exceeded
6	Execution timed out	1075 ms	13920 KB	Time limit exceeded
7	Execution timed out	1051 ms	13364 KB	Time limit exceeded
8	Execution timed out	1066 ms	13500 KB	Time limit exceeded
9	Correct	983 ms	16564 KB	Output is correct
10	Correct	724 ms	15960 KB	Output is correct
11	Correct	272 ms	14740 KB	Output is correct
12	Correct	360 ms	17588 KB	Output is correct
13	Correct	396 ms	18388 KB	Output is correct
14	Correct	381 ms	20020 KB	Output is correct
15	Correct	711 ms	21700 KB	Output is correct
16	Correct	422 ms	22424 KB	Output is correct
17	Correct	475 ms	26152 KB	Output is correct
18	Execution timed out	1054 ms	18368 KB	Time limit exceeded
19	Execution timed out	1063 ms	19080 KB	Time limit exceeded
20	Correct	427 ms	26132 KB	Output is correct