Submission #655300

#	Time	Username	Problem	Language	Result	Execution time	Memory
655300		quarna	Job Scheduling (CEOI12_jobs)	Java	0 / 100	151 ms	12408 KiB

jobs

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

class Main {
	static int n, d, m;
	static int[] jobs;
	public static void main(String[] args) throws IOException {
		BufferedReader r = new BufferedReader(new FileReader("jobs.in"));
		PrintWriter pw = new PrintWriter("jobs.out");

		StringTokenizer st = new StringTokenizer(r.readLine());
		n = Integer.parseInt(st.nextToken());
		d = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		jobs = new int[n + d];
		ArrayList<Integer>[] ids = new ArrayList[n]; 
		for (int i=0; i<n; i++){
			ids[i] = new ArrayList<Integer>();
		}
		st = new StringTokenizer(r.readLine());
		for (int i=0; i<m; i++){
			int day = Integer.parseInt(st.nextToken())-1;
			jobs[day]++;
			ids[day].add(i+1);
		}
		for (int i=1; i<n + d; i++){
			jobs[i] += jobs[i-1];
		}
		int lo = 1;
		int hi = m;
		while (lo < hi){
			int mid = (lo + hi) / 2;
			if (ok(mid)) hi = mid;
			else lo = mid + 1;
		}
		pw.println(lo);
		int total = 0;
		for (int i=0; i<n; i++){
			int count = 0;
			int ind = 0;
			while (count < lo && total < m){
				for (int j=0; j<ids[ind].size(); j++){
					if (count == lo) break;
					pw.print(ids[ind].get(j) + " ");
					count++;
					ids[ind].remove(j);
					j--;
				}
				ind++;
			}
			pw.println(0);
			total += count;
		}
		pw.close();
	}
	static boolean ok (int lim){
		int count = 0;
		int[] t = jobs.clone();
		for (int i=0; i<n + d; i++){
			int curr = Math.min(lim, Math.max(t[i], 0));
			count += curr;
			if (i < n + d - 1){
				t[i+1] -= curr;
			}
		}
		return count >= m;
	}
}

Compilation message (stderr)

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

• Subtask 1: 0 / 100