제출 #540919

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

jobs

import java.io.*;
import java.util.*;
public class jobs {
	public static int ans;
	public static City[]arr;
	public static int jobs;
	public static int maxdelay;
	public static int days;
	static class City{
		int time;
		int pos;
	}
	static class comp implements Comparator <City> { 
		public int compare(City c1, City c2) {
			if(c1.time < c2.time) {
				return -1;
			}
			return 1;
		}
	}
	public static void search(int start, int end) {
		//System.out.println(start + "  " + end);
		if(start == end) {
			ans = start;
			return;
		}
		int mid = (start + end)/2;
		if(works(mid)) {
			search(start, mid);
		}
		else {
			search(mid+1, end);
		}
	}
	public static boolean works(int nummachines) {
		int daysneeded = 1;
		int val  = arr[0].time;
		int i = 1;
		int used = 2;
		while(i < jobs) {
			while(i < jobs && used <= nummachines && arr[i].time <= val + maxdelay) {
				i++;
				used++;
			}
			if(i == jobs) {
				break;
			}
			val = arr[i].time;
			used = 1;
			daysneeded++;
			
		}
		return daysneeded <= days;
	}
	public static void main(String[]args) throws IOException{
		Kattio io = new Kattio();
		days = io.nextInt();
		maxdelay = io.nextInt();
		jobs = io.nextInt();
		ans = 0;
		arr = new City[jobs];
		for(int i = 0; i < jobs; i++) {
			arr[i] = new City();
			arr[i].time = io.nextInt();
			arr[i].pos = i+1;
		}
		Arrays.sort(arr, new comp());
		search(1, 1000000);
		int daysneeded = 1;
		int val  = arr[0].time;
		int i = 1;
		int startingindex = 0;
		int used = 2;
		io.println(ans);
		while(i < jobs) {
			while(i < jobs && used <= ans && arr[i].time <= val + maxdelay) {
				i++;
				used++;
			}
			if(i == jobs) {
				io.println(arr[startingindex].pos + " " + arr[i-1].pos + " " + 0);
				break;
			}
			io.println(arr[startingindex].pos + " " + arr[i-1].pos + " " + 0);
			val = arr[i].time;
			used = 1;
			startingindex = i;
			daysneeded++;
		}
		for(int m = 0; m < days - daysneeded; m++) {
			io.println("0");
		}
		io.close();
	}
	static class Kattio extends PrintWriter {
		private BufferedReader r;
		private StringTokenizer st = new StringTokenizer("");
		private String token;
 
		// 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(new FileWriter(problemName+".out"));
			r = new BufferedReader(new FileReader(problemName+".in"));
		}
 
		private String peek() {
			if (token == null)
				try {
					while (!st.hasMoreTokens()) {
						String line = r.readLine();
						if (line == null) return null;
						st = new StringTokenizer(line);
					}
					token = st.nextToken();
				} catch (IOException e) { }
			return token;
		}
		public boolean hasMoreTokens() { return peek() != null; }
		public String next() {
			String ans = peek(); 
			token = null;
			return ans;
		}
		
		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