Submission #305921

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
305921	2020-09-24T05:23:33 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;
	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	541 ms	43112 KB	Memory limit exceeded
2	Runtime error	543 ms	42752 KB	Memory limit exceeded
3	Runtime error	542 ms	43244 KB	Memory limit exceeded
4	Runtime error	521 ms	43032 KB	Memory limit exceeded
5	Runtime error	625 ms	43052 KB	Memory limit exceeded
6	Runtime error	519 ms	42908 KB	Memory limit exceeded
7	Runtime error	506 ms	42948 KB	Memory limit exceeded
8	Runtime error	525 ms	42860 KB	Memory limit exceeded
9	Runtime error	765 ms	41384 KB	Memory limit exceeded
10	Runtime error	756 ms	40272 KB	Memory limit exceeded
11	Runtime error	834 ms	42584 KB	Memory limit exceeded
12	Execution timed out	1070 ms	58032 KB	Time limit exceeded
13	Execution timed out	1040 ms	59988 KB	Time limit exceeded
14	Execution timed out	1115 ms	59300 KB	Time limit exceeded
15	Execution timed out	1027 ms	59780 KB	Time limit exceeded
16	Runtime error	484 ms	65548 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
17	Runtime error	496 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Runtime error	466 ms	65556 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Runtime error	446 ms	65548 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Runtime error	494 ms	65552 KB	Execution killed with signal 9 (could be triggered by violating memory limits)