Submission #1119443

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119443	2024-11-27T04:10:45 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	45 / 100	1000 ms	65536 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;
    public static void main(String[] args) throws IOException {
        int N = nextInt(), D = nextInt(), M = nextInt();
        HashSet<Integer>[] s = new HashSet[N + 1];
        for (int i = 1; i <= N; i++)
            s[i] = new HashSet<>();
        for (int i = 1; i <= M; i++)
            s[nextInt()].add(i);
        int L = 0, R = 1000000, m = 0;
        while (L < R) {
            m = (L + R) / 2;
            boolean b = true;
            int dd = 1, r = 0;
            for (int i = 1; i <= N; i++) {
                if (s[i].size() == 0)
                    continue;
                if (dd < i - D) {
                    dd = i - D;
                    r = 0;
                }
                dd += (s[i].size() + r) / m;
                r = (s[i].size() + r) % m;
                if (dd > i + 1 || dd == i + 1 && r > 0) {
                    b = false;
                    break;
                }
            }
            if (b)
                R = m;
            else
                L = m + 1;
        }
        System.out.println(m);
        ArrayDeque<Integer> a = new ArrayDeque<>();
        for (int i = 1; i <= N; i++) {
            for (int j : s[i])
                a.addLast(j);
            int cnt = 0;
            while (cnt++ < m && !a.isEmpty())
                System.out.print(a.pollFirst() + " ");
            System.out.println(0);
        }
    }
    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();
    }
}

Compilation message

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

Subtask #1

45.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	933 ms	29140 KB	Output is correct
2	Correct	917 ms	28352 KB	Output is correct
3	Correct	876 ms	28592 KB	Output is correct
4	Correct	870 ms	28644 KB	Output is correct
5	Correct	950 ms	28316 KB	Output is correct
6	Correct	910 ms	28336 KB	Output is correct
7	Correct	872 ms	28584 KB	Output is correct
8	Correct	910 ms	28648 KB	Output is correct
9	Execution timed out	1048 ms	38852 KB	Time limit exceeded
10	Execution timed out	1055 ms	34768 KB	Time limit exceeded
11	Correct	787 ms	23940 KB	Output is correct
12	Execution timed out	1040 ms	36960 KB	Time limit exceeded
13	Execution timed out	1073 ms	50408 KB	Time limit exceeded
14	Execution timed out	1073 ms	60836 KB	Time limit exceeded
15	Execution timed out	1056 ms	65536 KB	Time limit exceeded
16	Runtime error	582 ms	65536 KB	Execution killed with signal 9
17	Runtime error	606 ms	65536 KB	Execution killed with signal 9
18	Runtime error	651 ms	65536 KB	Execution killed with signal 9
19	Runtime error	469 ms	65536 KB	Execution killed with signal 9
20	Runtime error	605 ms	65536 KB	Execution killed with signal 9