답안 #305917

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
305917 2020-09-24T05:19:58 Z Celloboy Job Scheduling (CEOI12_jobs) Java 11
0 / 100
1000 ms 65540 KB
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;
		}
	}
}
# 결과 실행 시간 메모리 Grader output
1 Runtime error 502 ms 42600 KB Memory limit exceeded
2 Runtime error 557 ms 42084 KB Memory limit exceeded
3 Runtime error 472 ms 41552 KB Memory limit exceeded
4 Runtime error 514 ms 42584 KB Memory limit exceeded
5 Runtime error 542 ms 41360 KB Memory limit exceeded
6 Runtime error 547 ms 41880 KB Memory limit exceeded
7 Runtime error 589 ms 41028 KB Memory limit exceeded
8 Runtime error 560 ms 40576 KB Memory limit exceeded
9 Runtime error 731 ms 40072 KB Memory limit exceeded
10 Runtime error 834 ms 39664 KB Memory limit exceeded
11 Runtime error 876 ms 41520 KB Memory limit exceeded
12 Execution timed out 1180 ms 38876 KB Time limit exceeded
13 Execution timed out 1309 ms 60940 KB Time limit exceeded
14 Execution timed out 1016 ms 63744 KB Time limit exceeded
15 Execution timed out 1231 ms 62628 KB Time limit exceeded
16 Runtime error 436 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 413 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 419 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 488 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 416 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)