Submission #305912

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
305912	2020-09-24T05:12:17 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);
		}
		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[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
		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	Execution timed out	1108 ms	50092 KB	Time limit exceeded
2	Execution timed out	1016 ms	47384 KB	Time limit exceeded
3	Execution timed out	1180 ms	48072 KB	Time limit exceeded
4	Execution timed out	1027 ms	52044 KB	Time limit exceeded
5	Execution timed out	1073 ms	49436 KB	Time limit exceeded
6	Execution timed out	1035 ms	52184 KB	Time limit exceeded
7	Runtime error	971 ms	47236 KB	Memory limit exceeded
8	Execution timed out	1087 ms	51988 KB	Time limit exceeded
9	Execution timed out	1112 ms	40280 KB	Time limit exceeded
10	Execution timed out	1104 ms	46308 KB	Time limit exceeded
11	Execution timed out	1163 ms	38608 KB	Time limit exceeded
12	Execution timed out	1087 ms	38780 KB	Time limit exceeded
13	Execution timed out	1052 ms	59752 KB	Time limit exceeded
14	Execution timed out	1291 ms	62356 KB	Time limit exceeded
15	Execution timed out	1288 ms	62840 KB	Time limit exceeded
16	Execution timed out	1211 ms	63752 KB	Time limit exceeded
17	Runtime error	422 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Runtime error	455 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Runtime error	467 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Runtime error	517 ms	65548 KB	Execution killed with signal 9 (could be triggered by violating memory limits)