Submission #642351

#	Time	Username	Problem	Language	Result	Execution time	Memory
642351		accidentac	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1098 ms	62368 KiB

jobs

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

class jobs {
	static int[][] jobs;
	static int n, d, m;
	static List<List<Integer>> dummy() {
		List<List<Integer>> res = new ArrayList<>();
		res.add(new ArrayList<>());
		return res;
	}
	// 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, boolean formResult) {
		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][0] >= day) {
				r++;
			}
			List<Integer> cur = new ArrayList<>();
			int filled = 0;
			while (l < r && filled < count) {
				if (day - jobs[l][0] > d) return new ArrayList<>();
				if (formResult) cur.add(jobs[l][1]);
				finished++;
				l++;
				filled++;
			}
			if (formResult) res.add(cur);
		}
		if (formResult)
			return finished < m ? new ArrayList<>() : res;
		return finished < m ? new ArrayList<>() : dummy();
	}
	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][2];
		for (int i = 0; i < m; i++) {
			int day = io.nextInt();
			jobs[i][0] = day;
			jobs[i][1] = i + 1;
		}
		Arrays.sort(jobs, (a,b) -> Integer.compare(a[0], b[0]));
		int lo = 1, hi = m, best = m;
		while (lo <= hi) {
			int mid = lo + (hi - lo) / 2;
			if (!ok(mid, false).isEmpty()) {
				best = mid;
				hi = mid - 1;
			} else {
				lo = mid + 1;
			}
		}
		io.println(best);
		List<List<Integer>> ans = ok(best, true);
		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: 0 / 100