Submission #1119467

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119467	2024-11-27T05:04:25 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	70 ms	12028 KB

jobs

import java.io.*;
import java.util.*;

public class jobs {
    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);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken()); // Number of days
        int d = Integer.parseInt(st.nextToken()); // Delay allowed
        int m = Integer.parseInt(st.nextToken()); // Number of events

        Pair[] a = new Pair[m + 2];
        for (int i = 1; i <= m; i++) {
            int fr = Integer.parseInt(st.nextToken());
            a[i] = new Pair(fr, i); // Store event and its index
        }
        a[m + 1] = new Pair((int) 1e9, 0); // Add a dummy pair for boundary handling

        Arrays.sort(a, 1, m + 1); // Sort by the `fr` value

        int l = 0, r = m;

        // Binary search to find the minimum value of `r`
        while (r - l > 1) {
            int mid = (l + r) / 2;
            int p = 1;
            boolean valid = true;

            for (int i = 1; i <= n; i++) {
                if (p > m || a[p].fr + d < i) {
                    valid = false;
                    break;
                }
                int cnt = 0;
                while (cnt < mid && p <= m && a[p].fr <= i) {
                    cnt++;
                    p++;
                }
            }

            if (valid && p > m) {
                r = mid; // Valid with this `mid`
            } else {
                l = mid; // Not valid, increase `l`
            }
        }

        // Print the result
        System.out.println(r);
        int p = 1;
        StringBuilder sb = new StringBuilder();

        for (int i = 1; i <= n; i++) {
            int cnt = 0;
            while (cnt < r && p <= m && a[p].fr <= i) {
                sb.append(a[p].sc).append(" ");
                cnt++;
                p++;
            }
            sb.append(0).append("\n");
        }

        System.out.print(sb);
    }
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	57 ms	8908 KB	Execution failed because the return code was nonzero
2	Runtime error	56 ms	8852 KB	Execution failed because the return code was nonzero
3	Runtime error	59 ms	8916 KB	Execution failed because the return code was nonzero
4	Runtime error	54 ms	8880 KB	Execution failed because the return code was nonzero
5	Runtime error	64 ms	8848 KB	Execution failed because the return code was nonzero
6	Runtime error	64 ms	9044 KB	Execution failed because the return code was nonzero
7	Runtime error	53 ms	8796 KB	Execution failed because the return code was nonzero
8	Runtime error	56 ms	9196 KB	Execution failed because the return code was nonzero
9	Runtime error	54 ms	9148 KB	Execution failed because the return code was nonzero
10	Runtime error	57 ms	8732 KB	Execution failed because the return code was nonzero
11	Runtime error	55 ms	9212 KB	Execution failed because the return code was nonzero
12	Runtime error	58 ms	8944 KB	Execution failed because the return code was nonzero
13	Runtime error	64 ms	9712 KB	Execution failed because the return code was nonzero
14	Runtime error	60 ms	10012 KB	Execution failed because the return code was nonzero
15	Runtime error	62 ms	10264 KB	Execution failed because the return code was nonzero
16	Runtime error	70 ms	10992 KB	Execution failed because the return code was nonzero
17	Runtime error	58 ms	11956 KB	Execution failed because the return code was nonzero
18	Runtime error	59 ms	11764 KB	Execution failed because the return code was nonzero
19	Runtime error	67 ms	12028 KB	Execution failed because the return code was nonzero
20	Runtime error	57 ms	11560 KB	Execution failed because the return code was nonzero