Submission #306212

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
306212	2020-09-24T21:29:01 Z	Celloboy	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	65564 KB

jobs

import java.io.*;
import java.util.*;
 
 
public class jobs {
	static int N, D, M;
	static ArrayList<Group> arr;
	static int prevDay[];
	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 ArrayList<Group>();
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < M; i++) {
			arr.add(new Group(Integer.parseInt(st.nextToken()), i+1));
			//System.out.println(arr[i]);
		}
		Collections.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.get(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
		prevDay = new int[mid];
		for(int i = 0; i < M;) {
			for(int j = i; j < i +mid; j++) {
				if(j >= M) {
					break;
				}
				if(arr.get(j).a> prevDay[j-i]) {
					prevDay[j-i] = arr.get(j).a;
				}else {
					int temp = prevDay[j-i]-arr.get(j).a+1;
					if(temp > D) {
						return false;
					}
					prevDay[j-i] = temp+prevDay[j-i];
				}
			}
			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	Execution timed out	1116 ms	53152 KB	Time limit exceeded
2	Execution timed out	1004 ms	50508 KB	Time limit exceeded
3	Runtime error	969 ms	50648 KB	Memory limit exceeded
4	Runtime error	982 ms	51708 KB	Memory limit exceeded
5	Execution timed out	1022 ms	50900 KB	Time limit exceeded
6	Execution timed out	1006 ms	54600 KB	Time limit exceeded
7	Execution timed out	1040 ms	54596 KB	Time limit exceeded
8	Execution timed out	1053 ms	50844 KB	Time limit exceeded
9	Execution timed out	1061 ms	45488 KB	Time limit exceeded
10	Execution timed out	1038 ms	42988 KB	Time limit exceeded
11	Execution timed out	1074 ms	39944 KB	Time limit exceeded
12	Execution timed out	1105 ms	47696 KB	Time limit exceeded
13	Execution timed out	1016 ms	59488 KB	Time limit exceeded
14	Execution timed out	1131 ms	59296 KB	Time limit exceeded
15	Execution timed out	1131 ms	59784 KB	Time limit exceeded
16	Runtime error	464 ms	65548 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
17	Runtime error	485 ms	65552 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Runtime error	422 ms	65548 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Runtime error	428 ms	65552 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Runtime error	439 ms	65564 KB	Execution killed with signal 9 (could be triggered by violating memory limits)