Submission #305928

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
305928	2020-09-24T05:27:05 Z	Celloboy	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	65556 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	324 ms	26900 KB	Unexpected end of file - int32 expected
2	Incorrect	348 ms	26912 KB	Unexpected end of file - int32 expected
3	Incorrect	339 ms	28036 KB	Unexpected end of file - int32 expected
4	Incorrect	318 ms	27020 KB	Unexpected end of file - int32 expected
5	Incorrect	359 ms	26820 KB	Unexpected end of file - int32 expected
6	Incorrect	335 ms	26620 KB	Unexpected end of file - int32 expected
7	Incorrect	321 ms	26780 KB	Unexpected end of file - int32 expected
8	Incorrect	356 ms	27072 KB	Unexpected end of file - int32 expected
9	Incorrect	603 ms	27380 KB	Unexpected end of file - int32 expected
10	Incorrect	605 ms	26628 KB	Output isn't correct
11	Incorrect	593 ms	28552 KB	Unexpected end of file - int32 expected
12	Runtime error	756 ms	39772 KB	Memory limit exceeded
13	Runtime error	930 ms	59912 KB	Memory limit exceeded
14	Execution timed out	1036 ms	59240 KB	Time limit exceeded
15	Execution timed out	1080 ms	59968 KB	Time limit exceeded
16	Runtime error	480 ms	65548 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
17	Runtime error	463 ms	65544 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Runtime error	530 ms	65556 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Runtime error	525 ms	65548 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Runtime error	444 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)