Submission #305930

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

jobs

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


public class jobs {
	static int N, D, M;
	static ArrayList<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 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);
		}
		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.get(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;
				}
				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	Runtime error	586 ms	42880 KB	Memory limit exceeded
2	Runtime error	568 ms	42436 KB	Memory limit exceeded
3	Runtime error	495 ms	42624 KB	Memory limit exceeded
4	Runtime error	590 ms	42936 KB	Memory limit exceeded
5	Runtime error	580 ms	42904 KB	Memory limit exceeded
6	Runtime error	598 ms	42948 KB	Memory limit exceeded
7	Runtime error	555 ms	42632 KB	Memory limit exceeded
8	Runtime error	609 ms	43144 KB	Memory limit exceeded
9	Runtime error	782 ms	41640 KB	Memory limit exceeded
10	Runtime error	825 ms	40564 KB	Memory limit exceeded
11	Runtime error	815 ms	41576 KB	Memory limit exceeded
12	Execution timed out	1065 ms	56668 KB	Time limit exceeded
13	Execution timed out	1046 ms	59256 KB	Time limit exceeded
14	Execution timed out	1146 ms	58844 KB	Time limit exceeded
15	Execution timed out	1110 ms	60236 KB	Time limit exceeded
16	Runtime error	445 ms	65544 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
17	Runtime error	453 ms	65548 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Runtime error	515 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Runtime error	451 ms	65548 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Runtime error	432 ms	65548 KB	Execution killed with signal 9 (could be triggered by violating memory limits)