Submission #1311645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311645		rs28	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1082 ms	131072 KiB

jobs

import java.util.*;

public class jobs {

	static class pnt implements Comparable<pnt> {
		public int day;
		public int id;

		public pnt(int day, int id) {
			this.day = day;
			this.id = id;
		}

		@Override
		public int compareTo(pnt o) {
			if (this.day != o.day) {
				return Integer.compare(this.day, o.day);
			}
			return Integer.compare(this.id, o.id);
		}
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		if (!in.hasNext())
			return;

		int n = in.nextInt();
		int d = in.nextInt();
		int m = in.nextInt();

		pnt[] js = new pnt[m];
		for (int i = 0; i < m; i++) {
			js[i] = new pnt(in.nextInt(), i + 1);
		}

		Arrays.sort(js);

		int a = 1;
		int b = m;

		while (a != b) {
			int mid = (a + b) / 2;
			if (checks(mid, js, d)) {
				b = mid;
			} else {
				a = mid + 1;
			}
		}

		System.out.println(a);

		StringBuilder[] days = new StringBuilder[n + 1];
		for (int i = 1; i <= n; i++) {
			days[i] = new StringBuilder();
		}

		PriorityQueue<Integer> pq = new PriorityQueue<>();

		for (pnt ii : js) {
			int i = ii.day;
			int t;

			if (pq.size() < a) {
				t = 0;
			} else {
				t = pq.poll();
			}

			int st = Math.max(t, i);

			days[st].append(ii.id).append(" ");

			pq.add(st + 1);
		}

		for (int i = 1; i <= n; i++) {
			days[i].append("0");
			System.out.println(days[i]);
		}
	}

	public static boolean checks(int limit, pnt[] js, int d) {
		PriorityQueue<Integer> pq = new PriorityQueue<>();

		for (pnt ii : js) {
			int i = ii.day;
			int t;

			if (pq.size() < limit) {
				t = 0;
			} else {
				t = pq.poll();
			}

			int st = Math.max(t, i);

			if (st - i > d) {
				return false;
			}

			pq.add(st + 1);
		}
		return true;
	}

}

• Subtask 1: 0 / 100