Submission #305917

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
305917	2020-09-24T05:19:58 Z	Celloboy	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	65540 KB

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);
		}
		pw.println(a);
		int point1 = 0;
		for(int i = 0; i < N; i++) {
			int curr = point1 + a;
			while(point1 < M && point1 < curr) {
				pw.print(arr[point1].b + " ");
				point1++;
			}
			pw.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.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	502 ms	42600 KB	Memory limit exceeded
2	Runtime error	557 ms	42084 KB	Memory limit exceeded
3	Runtime error	472 ms	41552 KB	Memory limit exceeded
4	Runtime error	514 ms	42584 KB	Memory limit exceeded
5	Runtime error	542 ms	41360 KB	Memory limit exceeded
6	Runtime error	547 ms	41880 KB	Memory limit exceeded
7	Runtime error	589 ms	41028 KB	Memory limit exceeded
8	Runtime error	560 ms	40576 KB	Memory limit exceeded
9	Runtime error	731 ms	40072 KB	Memory limit exceeded
10	Runtime error	834 ms	39664 KB	Memory limit exceeded
11	Runtime error	876 ms	41520 KB	Memory limit exceeded
12	Execution timed out	1180 ms	38876 KB	Time limit exceeded
13	Execution timed out	1309 ms	60940 KB	Time limit exceeded
14	Execution timed out	1016 ms	63744 KB	Time limit exceeded
15	Execution timed out	1231 ms	62628 KB	Time limit exceeded
16	Runtime error	436 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
17	Runtime error	413 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Runtime error	419 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Runtime error	488 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Runtime error	416 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)