Submission #305913

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
305913	2020-09-24T05:15:25 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 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	537 ms	41668 KB	Memory limit exceeded
2	Runtime error	563 ms	42564 KB	Memory limit exceeded
3	Runtime error	477 ms	41872 KB	Memory limit exceeded
4	Runtime error	494 ms	41692 KB	Memory limit exceeded
5	Runtime error	500 ms	41924 KB	Memory limit exceeded
6	Runtime error	543 ms	41576 KB	Memory limit exceeded
7	Runtime error	514 ms	42108 KB	Memory limit exceeded
8	Runtime error	454 ms	41836 KB	Memory limit exceeded
9	Runtime error	772 ms	40296 KB	Memory limit exceeded
10	Runtime error	822 ms	41040 KB	Memory limit exceeded
11	Runtime error	861 ms	40988 KB	Memory limit exceeded
12	Execution timed out	1116 ms	39276 KB	Time limit exceeded
13	Execution timed out	1268 ms	60544 KB	Time limit exceeded
14	Execution timed out	1026 ms	62404 KB	Time limit exceeded
15	Execution timed out	1049 ms	62944 KB	Time limit exceeded
16	Runtime error	528 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
17	Runtime error	418 ms	65548 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Runtime error	436 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Runtime error	393 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Runtime error	429 ms	65548 KB	Execution killed with signal 9 (could be triggered by violating memory limits)