Submission #1119445

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119445	2024-11-27T04:21:55 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	50 / 100	1000 ms	64364 KB

jobs

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

public class jobs {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    static StringTokenizer st;
    static String next() throws IOException {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine().trim());
        return st.nextToken();
    }
    static char nextChar() throws IOException {
        return next().charAt(0);
    }
    static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
    static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
    static long nextLong() throws IOException {
        return Long.parseLong(next());
    }
    static String nextLine() throws IOException {
        return br.readLine().trim();
    }
    static final int MAXN = 100001;
    static int[] Cn = new int[MAXN];
    static List<Integer>[] Req = new ArrayList[MAXN];
    static int n, m, d;

    public static boolean test(int k) {
        int dd = 1, r = 0;
        for (int x = 1; x <= n; x++) {
            if (Cn[x] == 0) continue;
            if (dd < x - d) {
                dd = x - d;
                r = 0;
            }
            dd += (Cn[x] + r) / k;
            r = (Cn[x] + r) % k;
            if (dd > x + 1 || (dd == x + 1 && r > 0)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        n = nextInt();
        d = nextInt();
        m = nextInt();

        for (int x = 0; x <= n; x++) {
            Req[x] = new ArrayList<>();
            Cn[x] = 0;
        }

        for (int i = 0; i < m; i++) {
            int a = nextInt() + d;
            Req[a].add(i + 1);
            Cn[a]++;
        }

        // Compute lower and upper bounds for binary search
        int left = 1, sol = 0, r = 0;
        for (int x = 1; x <= n; x++) {
            if (Cn[x] == 0) {
                if (r <= d) r++;
            } else {
                if ((Cn[x] + d) / (d + 1) > left) {
                    left = (Cn[x] + d) / (d + 1);
                }
                if (r * sol >= Cn[x]) {
                    r -= (Cn[x] + sol - 1) / sol;
                    r++;
                } else {
                    sol += (Cn[x] - r * sol + d) / (d + 1);
                    r = 1;
                }
            }
        }

        // Binary search to find the solution
        while (left < sol) {
            int mid = (left + sol) / 2;
            if (test(mid)) {
                sol = mid;
            } else {
                left = mid + 1;
            }
        }

        System.out.println(sol);

        // Output the schedule
        int dc = 1, dd = 1, x = 1;
        Iterator<Integer> p = Req[1].iterator();

        while (dd <= n) {
            if (!p.hasNext()) {
                x++;
                while (x <= n && Req[x].isEmpty()) x++;
                if (x > n) break;
                p = Req[x].iterator();
            }

            if (dd < x - d) {
                System.out.println("0");
                dd++;
                dc = 1;
            } else {
                System.out.print(p.next() + " ");
                if (++dc > sol) {
                    dc = 1;
                    dd++;
                    System.out.println("0");
                }
            }
        }

        if (dc > 1) {
            dd++;
            System.out.println("0");
        }
        while (dd++ <= n) {
            System.out.println("0");
        }
    }
}

Compilation message

Note: jobs.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Subtask #1

50.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	774 ms	19908 KB	Output is correct
2	Correct	776 ms	19644 KB	Output is correct
3	Correct	815 ms	19924 KB	Output is correct
4	Correct	790 ms	20176 KB	Output is correct
5	Correct	798 ms	20156 KB	Output is correct
6	Correct	719 ms	19720 KB	Output is correct
7	Correct	746 ms	19656 KB	Output is correct
8	Correct	796 ms	19704 KB	Output is correct
9	Execution timed out	1055 ms	23032 KB	Time limit exceeded
10	Execution timed out	1062 ms	23340 KB	Time limit exceeded
11	Correct	711 ms	19980 KB	Output is correct
12	Correct	960 ms	25248 KB	Output is correct
13	Execution timed out	1054 ms	30260 KB	Time limit exceeded
14	Execution timed out	1064 ms	36500 KB	Time limit exceeded
15	Execution timed out	1062 ms	38752 KB	Time limit exceeded
16	Execution timed out	1042 ms	46976 KB	Time limit exceeded
17	Execution timed out	1045 ms	51484 KB	Time limit exceeded
18	Execution timed out	1062 ms	53068 KB	Time limit exceeded
19	Execution timed out	1052 ms	64364 KB	Time limit exceeded
20	Execution timed out	1054 ms	51712 KB	Time limit exceeded