답안 #305930

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
305930 2020-09-24T05:31:42 Z Celloboy Job Scheduling (CEOI12_jobs) Java 11
0 / 100
1000 ms 65548 KB
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;
		}
	}
}
# 결과 실행 시간 메모리 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)