Submission #1119464

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119464	2024-11-27T05:00:12 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	150 ms	26088 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++) {
            st = new StringTokenizer(br.readLine());
            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	131 ms	14340 KB	Execution failed because the return code was nonzero
2	Runtime error	129 ms	14744 KB	Execution failed because the return code was nonzero
3	Runtime error	125 ms	14444 KB	Execution failed because the return code was nonzero
4	Runtime error	126 ms	14448 KB	Execution failed because the return code was nonzero
5	Runtime error	122 ms	14364 KB	Execution failed because the return code was nonzero
6	Runtime error	122 ms	14728 KB	Execution failed because the return code was nonzero
7	Runtime error	142 ms	14480 KB	Execution failed because the return code was nonzero
8	Runtime error	128 ms	14612 KB	Execution failed because the return code was nonzero
9	Runtime error	119 ms	12600 KB	Execution failed because the return code was nonzero
10	Runtime error	128 ms	12708 KB	Execution failed because the return code was nonzero
11	Runtime error	127 ms	14288 KB	Execution failed because the return code was nonzero
12	Runtime error	124 ms	15744 KB	Execution failed because the return code was nonzero
13	Runtime error	121 ms	17860 KB	Execution failed because the return code was nonzero
14	Runtime error	122 ms	19896 KB	Execution failed because the return code was nonzero
15	Runtime error	135 ms	18736 KB	Execution failed because the return code was nonzero
16	Runtime error	135 ms	22892 KB	Execution failed because the return code was nonzero
17	Runtime error	135 ms	26088 KB	Execution failed because the return code was nonzero
18	Runtime error	150 ms	25300 KB	Execution failed because the return code was nonzero
19	Runtime error	147 ms	25324 KB	Execution failed because the return code was nonzero
20	Runtime error	128 ms	23940 KB	Execution failed because the return code was nonzero