제출 #292337

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
292337		R3KT	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1782 ms	65552 KiB

jobs

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

public class jobs {

	// https://oj.uz/problem/view/CEOI12_jobs
	
	// TLE && RTE
	public static void main(String[] args) throws IOException, FileNotFoundException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		//BufferedReader in = new BufferedReader(new FileReader("jobs"));

		StringTokenizer st = new StringTokenizer(in.readLine());
		int n = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		obj[] arr = new obj[m];
		st = new StringTokenizer(in.readLine());
		for (int i=0; i<m; ++i) {
			int v = Integer.parseInt(st.nextToken());
			arr[i] = new obj(v, i+1);
		}
		Arrays.parallelSort(arr);
		
		int min=0;
		int max=m;
		while (min < max) {
			int middle = (min + max)/2;
			if (check(arr, middle, d, n)) {
				max = middle;
			}
			else min = middle+1;
		}
		
		/*
		System.out.println(min);
		// construct
		int count=1;
		for (int i=0; i<m; i+=min) {
			for (int j=i; j<i+min && j<m; j++) {
				System.out.print(arr[j].pos + " ");
			}
			System.out.println(0);
			count++;
		}
		for (int i=count; i<=n; i++) System.out.println(0);
		*/
	}
	
	public static boolean check(obj[] arr, int num, int d, int n) {
		int pointer=0;
		int m = arr.length;
		for (int i=1; i<=n; i++) {
			if (pointer>=m) break;
			if (i - arr[pointer].val > d) return false;
			pointer += num;
		}
		if (pointer < m) return false;
		return true;
	}
	
	static class obj implements Comparable<obj> {
		int pos;
		int val;
		obj (int a, int b) {
			val = a;
			pos = b;
		}
		
		public int compareTo(obj other) {
			return val - other.val;
		}
	}
}

• Subtask 1: 0 / 100