Submission #305912

# Submission time Handle Problem Language Result Execution time Memory
305912 2020-09-24T05:12:17 Z Celloboy Job Scheduling (CEOI12_jobs) Java 11
0 / 100
1000 ms 65548 KB

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;
		}
	}
}
# Verdict Execution time Memory Grader output
1 Execution timed out 1108 ms 50092 KB Time limit exceeded
2 Execution timed out 1016 ms 47384 KB Time limit exceeded
3 Execution timed out 1180 ms 48072 KB Time limit exceeded
4 Execution timed out 1027 ms 52044 KB Time limit exceeded
5 Execution timed out 1073 ms 49436 KB Time limit exceeded
6 Execution timed out 1035 ms 52184 KB Time limit exceeded
7 Runtime error 971 ms 47236 KB Memory limit exceeded
8 Execution timed out 1087 ms 51988 KB Time limit exceeded
9 Execution timed out 1112 ms 40280 KB Time limit exceeded
10 Execution timed out 1104 ms 46308 KB Time limit exceeded
11 Execution timed out 1163 ms 38608 KB Time limit exceeded
12 Execution timed out 1087 ms 38780 KB Time limit exceeded
13 Execution timed out 1052 ms 59752 KB Time limit exceeded
14 Execution timed out 1291 ms 62356 KB Time limit exceeded
15 Execution timed out 1288 ms 62840 KB Time limit exceeded
16 Execution timed out 1211 ms 63752 KB Time limit exceeded
17 Runtime error 422 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 455 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 467 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 517 ms 65548 KB Execution killed with signal 9 (could be triggered by violating memory limits)