oj.uz

답안 #305933

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
305933 2020-09-24T05:52:12 Z Celloboy Job Scheduling (CEOI12_jobs) Java 11
0 / 100
 1000 ms 65556 KB 

import java.io.*;
import java.util.*;


public class jobs {
	static int N, D, M;
	static ArrayList<Group> arr;
	static int prevDay[];
	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
		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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 620 ms 43200 KB Memory limit exceeded
2 Runtime error 588 ms 43260 KB Memory limit exceeded
3 Runtime error 640 ms 43020 KB Memory limit exceeded
4 Runtime error 635 ms 42704 KB Memory limit exceeded
5 Runtime error 569 ms 42568 KB Memory limit exceeded
6 Runtime error 555 ms 43272 KB Memory limit exceeded
7 Runtime error 516 ms 42664 KB Memory limit exceeded
8 Runtime error 539 ms 42696 KB Memory limit exceeded
9 Runtime error 830 ms 41656 KB Memory limit exceeded
10 Runtime error 794 ms 40356 KB Memory limit exceeded
11 Runtime error 768 ms 42100 KB Memory limit exceeded
12 Execution timed out 1016 ms 53812 KB Time limit exceeded
13 Execution timed out 1026 ms 59768 KB Time limit exceeded
14 Execution timed out 1101 ms 60176 KB Time limit exceeded
15 Execution timed out 1080 ms 60052 KB Time limit exceeded
16 Runtime error 427 ms 65544 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 546 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 491 ms 65556 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 448 ms 65552 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 470 ms 65548 KB Execution killed with signal 9 (could be triggered by violating memory limits)