답안 #306211

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
306211	2020-09-24T21:27:49 Z	Celloboy	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	65552 KB

jobs

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);
		}
		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.get(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
		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	Execution timed out	1061 ms	54784 KB	Time limit exceeded
2	Execution timed out	1016 ms	52764 KB	Time limit exceeded
3	Runtime error	997 ms	50812 KB	Memory limit exceeded
4	Execution timed out	1034 ms	53892 KB	Time limit exceeded
5	Execution timed out	1059 ms	52224 KB	Time limit exceeded
6	Runtime error	949 ms	51824 KB	Memory limit exceeded
7	Runtime error	978 ms	50952 KB	Memory limit exceeded
8	Runtime error	994 ms	51940 KB	Memory limit exceeded
9	Execution timed out	1112 ms	46224 KB	Time limit exceeded
10	Execution timed out	1028 ms	42860 KB	Time limit exceeded
11	Execution timed out	1024 ms	44528 KB	Time limit exceeded
12	Execution timed out	1006 ms	48716 KB	Time limit exceeded
13	Execution timed out	1018 ms	60648 KB	Time limit exceeded
14	Execution timed out	1170 ms	61352 KB	Time limit exceeded
15	Execution timed out	1093 ms	61540 KB	Time limit exceeded
16	Runtime error	443 ms	65552 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
17	Runtime error	430 ms	65548 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Runtime error	420 ms	65548 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Runtime error	450 ms	65548 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Runtime error	457 ms	65552 KB	Execution killed with signal 9 (could be triggered by violating memory limits)