Submission #305923

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
305923	2020-09-24T05:24:59 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;
	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;
		}
	}
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	344 ms	26864 KB	Unexpected end of file - int32 expected
2	Incorrect	321 ms	26784 KB	Unexpected end of file - int32 expected
3	Incorrect	362 ms	27444 KB	Unexpected end of file - int32 expected
4	Incorrect	309 ms	26792 KB	Unexpected end of file - int32 expected
5	Incorrect	340 ms	26880 KB	Unexpected end of file - int32 expected
6	Incorrect	308 ms	26528 KB	Unexpected end of file - int32 expected
7	Incorrect	345 ms	28136 KB	Unexpected end of file - int32 expected
8	Incorrect	315 ms	26848 KB	Unexpected end of file - int32 expected
9	Incorrect	501 ms	26284 KB	Unexpected end of file - int32 expected
10	Incorrect	508 ms	26212 KB	Unexpected end of file - int32 expected
11	Incorrect	538 ms	27408 KB	Unexpected end of file - int32 expected
12	Runtime error	764 ms	40040 KB	Memory limit exceeded
13	Execution timed out	1056 ms	59496 KB	Time limit exceeded
14	Execution timed out	1051 ms	59388 KB	Time limit exceeded
15	Execution timed out	1118 ms	59892 KB	Time limit exceeded
16	Runtime error	513 ms	65548 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
17	Runtime error	446 ms	65552 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Runtime error	508 ms	65548 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Runtime error	434 ms	65548 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Runtime error	544 ms	65544 KB	Execution killed with signal 9 (could be triggered by violating memory limits)