Submission #305933

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
305933	2020-09-24T05:52:12 Z	Celloboy	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	65556 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);
		}
		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
		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	620 ms	43200 KB	Memory limit exceeded
2	Runtime error	588 ms	43260 KB	Memory limit exceeded
3	Runtime error	640 ms	43020 KB	Memory limit exceeded
4	Runtime error	635 ms	42704 KB	Memory limit exceeded
5	Runtime error	569 ms	42568 KB	Memory limit exceeded
6	Runtime error	555 ms	43272 KB	Memory limit exceeded
7	Runtime error	516 ms	42664 KB	Memory limit exceeded
8	Runtime error	539 ms	42696 KB	Memory limit exceeded
9	Runtime error	830 ms	41656 KB	Memory limit exceeded
10	Runtime error	794 ms	40356 KB	Memory limit exceeded
11	Runtime error	768 ms	42100 KB	Memory limit exceeded
12	Execution timed out	1016 ms	53812 KB	Time limit exceeded
13	Execution timed out	1026 ms	59768 KB	Time limit exceeded
14	Execution timed out	1101 ms	60176 KB	Time limit exceeded
15	Execution timed out	1080 ms	60052 KB	Time limit exceeded
16	Runtime error	427 ms	65544 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
17	Runtime error	546 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Runtime error	491 ms	65556 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Runtime error	448 ms	65552 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Runtime error	470 ms	65548 KB	Execution killed with signal 9 (could be triggered by violating memory limits)