제출 #666551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
666551		bruhgamer	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1087 ms	56960 KiB

jobs

import java.util.*;
import java.io.*;
public class jobs {
	public static int n;
	public static int d;
	public static Edge[]arr;
	public static int ans = 0;
	static class Edge implements Comparable<Edge> {
		int pos, val;
		public Edge(int _a, int _b) { pos = _a; val = _b;  }
		public int compareTo(Edge y) { return Integer.compare(val,y.val); }
	}
	public static void search(int start, int end) {
		if(start == end) {
			ans = start;
			return;
		}
		int mid = (start + end - 1)/2;
		if(works(mid)) {
			search(start, mid);
		}
		else {
			search(mid+1, end);
		}
	}
	public static boolean works(int machines) {
		int arrpos = 0;
		for(int i = 1; i <= n; i++) {
			int machinesused = 0;
			while(arrpos < arr.length && arr[arrpos].val <= i && machinesused < machines) {
				if(i - arr[arrpos].val > d) {
					return false;
				}
				machinesused++;
				arrpos++;
			}
			if(arrpos == arr.length) {
				break;
			}
		}
		if(arrpos < arr.length) {
			return false;
		}
		return true;
	}
	public static void main(String[]args) throws IOException{
		Kattio io = new Kattio();
		n = io.nextInt();
		d = io.nextInt();
		int m = io.nextInt();
		arr = new Edge[m];
		for(int i = 0; i < m; i++) {
			arr[i] = new Edge(i+1, io.nextInt());
		}
		Arrays.sort(arr);
		search(0, m);
		int arrpos = 0;
		for(int i = 1; i <= n; i++) {
			int machinesused = 0;
			while(arrpos < arr.length && arr[arrpos].val <= i && machinesused < ans) {
				io.print(arr[arrpos].pos + " ");
				machinesused++;
				arrpos++;
			}
			io.println("0");
		}
		io.close();
	}
	static class Kattio extends PrintWriter {
		private BufferedReader r;
		private StringTokenizer st;
		// standard input
		public Kattio() { this(System.in, System.out); }
		public Kattio(InputStream i, OutputStream o) {
			super(o);
			r = new BufferedReader(new InputStreamReader(i));
		}
		// USACO-style file input
		public Kattio(String problemName) throws IOException {
			super(problemName + ".out");
			r = new BufferedReader(new FileReader(problemName + ".in"));
		}
		// returns null if no more input
		public String next() {
			try {
				while (st == null || !st.hasMoreTokens())
					st = new StringTokenizer(r.readLine());
				return st.nextToken();
			} catch (Exception e) { }
			return null;
		}
		public int nextInt() { return Integer.parseInt(next()); }
		public double nextDouble() { return Double.parseDouble(next()); }
		public long nextLong() { return Long.parseLong(next()); }
	}
		
}

• Subtask 1: 0 / 100