Submission #1119483

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119483	2024-11-27T05:14:10 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	60 / 100	1000 ms	51860 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

        Pair[] a = new Pair[m + 1];
        for (int i = 1; i <= m; i++) {
            a[i] = new Pair(reader.nextInt(), i);
        }

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

        int l = 0, r = m;

        // Binary search
        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;
            }
        }

        System.out.println(r);
        int p = 1;

        // Fast output using BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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();
    }

    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);
        }
    }

    // Custom fast input reader
    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

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	258 ms	21040 KB	Output is correct
2	Correct	269 ms	19064 KB	Output is correct
3	Correct	263 ms	19196 KB	Output is correct
4	Correct	268 ms	19060 KB	Output is correct
5	Correct	260 ms	19184 KB	Output is correct
6	Correct	264 ms	19220 KB	Output is correct
7	Correct	263 ms	18844 KB	Output is correct
8	Correct	256 ms	19284 KB	Output is correct
9	Correct	798 ms	20568 KB	Output is correct
10	Correct	828 ms	22756 KB	Output is correct
11	Correct	865 ms	20756 KB	Output is correct
12	Correct	896 ms	26648 KB	Output is correct
13	Execution timed out	1016 ms	30664 KB	Time limit exceeded
14	Runtime error	982 ms	36728 KB	Memory limit exceeded
15	Execution timed out	1076 ms	33840 KB	Time limit exceeded
16	Execution timed out	1062 ms	36556 KB	Time limit exceeded
17	Execution timed out	1055 ms	41196 KB	Time limit exceeded
18	Execution timed out	1061 ms	41276 KB	Time limit exceeded
19	Execution timed out	1070 ms	51860 KB	Time limit exceeded
20	Execution timed out	1054 ms	38368 KB	Time limit exceeded