Submission #1119444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119444		johu	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1082 ms	65536 KiB

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 = 10000, 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 (stderr)

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

• Subtask 1: 0 / 100