Submission #305912

#	Time	Username	Problem	Language	Result	Execution time	Memory
305912		Celloboy	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1291 ms	65548 KiB

jobs

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


public class jobs {
	static int N, D, M;
	static Group arr[];
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//PrintWriter pw = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new Group[M];
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < M; i++) {
			arr[i] = new Group(Integer.parseInt(st.nextToken()), i+1);
			//System.out.println(arr[i]);
		}
		Arrays.sort(arr);
		int a = 0, b = M;
		while(a!=b) {
			int mid = (a+b)/2;
			if(works(mid)) {
				b=mid;
			}else {
				a=mid+1;
			}
			//System.out.println(a+" "+ b);
		}
		System.out.println(a);
		int point1 = 0;
		for(int i = 0; i < N; i++) {
			int curr = point1 + a;
			while(point1 < M && point1 < curr) {
				System.out.print(arr[point1].b + " ");
				point1++;
			}
			System.out.println("0");
		}
		//System.out.println(a);
		//pw.println(a);
	}
	private static boolean works(int mid) {
		// TODO Auto-generated method stub
		int prevDay[] = new int[mid];
		for(int i = 0; i < M;) {
			for(int j = i; j < i +mid; j++) {
				if(j >= M) {
					break;
				}
				//System.out.println(arr[j].a +" " + prevDay[j-i]+" " + j +" " + i);
				if(arr[j].a> prevDay[j-i]) {
					prevDay[j-i] = arr[j].a;
				}else {
					int temp = prevDay[j-i]-arr[j].a+1;
					if(temp > D) {
						return false;
					}
					prevDay[j-i] = temp+prevDay[j-i];
					//System.out.println(temp);
				}
			}
			i+=mid;
			if(i  >= M) {
				break;
			}
		}
		return true;
	}
	public static class Group implements Comparable<Group> {
		int a,b;

		// Constructor
		public Group(int a, int b) {
			this.a = a;
			this.b = b;
		}
		public String toString() 
	    { 
	        return this.a + " " + this.b; 
	    } 
		@Override
		public int compareTo(Group other) {
			return (int) (a-other.a);
		}
		@Override
		public boolean equals(Object other) {
			Group that = (Group) other;
			return that.b ==b;
		}
	}
}

• Subtask 1: 0 / 100