Submission #642307

#	Time	Username	Problem	Language	Result	Execution time	Memory
642307		accidentac	Job Scheduling (CEOI12_jobs)	Java	6 / 100	1096 ms	65536 KiB

jobs

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

class jobs {
	static int[] jobs;
	static int n, d, m;
	// return non-empty result if there is a way to use `count` number of machine
	// to finish all jobs under time-limit
	static List<List<Integer>> ok(int count) {
		List<List<Integer>> res = new ArrayList<>();
		int finished = 0;
		for (int day = 1, l = 0, r = 0; day <= n; day++) {
			while (r < m && jobs[r] >= day) {
				r++;
			}
			List<Integer> cur = new ArrayList<>();
			while (l < r && cur.size() < count) {
				if (day - jobs[l] > d) return new ArrayList<>();
				cur.add(jobs[l++]);
				finished++;
			}
			res.add(cur);
		}
		return finished < m ? new ArrayList<>() : res;
	}
	public static void main (String[] args) throws java.lang.Exception {
		Kattio io = new Kattio();
		n = io.nextInt();
		d = io.nextInt();
		m = io.nextInt();
		jobs = new int[m];
		for (int i = 0; i < m; i++) jobs[i] = io.nextInt();
		Arrays.sort(jobs);
		int lo = 1, hi = m, best = m;
		while (lo <= hi) {
			int mid = lo + (hi - lo) / 2;
			if (!ok(mid).isEmpty()) {
				best = mid;
				hi = mid - 1;
			} else {
				lo = mid + 1;
			}
		}
		io.println(best);
		List<List<Integer>> ans = ok(best);
		for (List<Integer> row : ans) {
			for (int x : row) {
				io.print(x + " ");
			}
			io.println(0);
		}
		io.close();
	}
}

class Kattio extends PrintWriter {

	private BufferedReader r;

	private StringTokenizer st;

	// standard input

	public Kattio() { this(System.in,System.out); }

	public Kattio(InputStream i, OutputStream o) {

		super(o);

		r = new BufferedReader(new InputStreamReader(i));

	}

	// USACO-style file input

	public Kattio(String problemName) throws IOException {

		super(problemName+".out");

		r = new BufferedReader(new FileReader(problemName+".in"));

	}

	// returns null if no more input

	public String next() {

		try {

			while (st == null || !st.hasMoreTokens())

				st = new StringTokenizer(r.readLine());

			return st.nextToken();

		} catch (Exception e) {}

		return null;

	}

	public int nextInt() { return Integer.parseInt(next()); }

	public double nextDouble() { return Double.parseDouble(next()); }

	public long nextLong() { return Long.parseLong(next()); }

}

• Subtask 1: 6 / 100