Submission #540910

#	Time	Username	Problem	Language	Result	Execution time	Memory
540910		bruhgamer	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1073 ms	57760 KiB

jobs

//package USACO;
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{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tokenizer = new StringTokenizer(in.readLine());
		days = Integer.parseInt(tokenizer.nextToken());
		maxdelay = Integer.parseInt(tokenizer.nextToken());
		jobs = Integer.parseInt(tokenizer.nextToken());
		ans = 0;
		arr = new City[jobs];
		tokenizer = new StringTokenizer(in.readLine());
		for(int i = 0; i < jobs; i++) {
			arr[i] = new City();
			arr[i].time = Integer.parseInt(tokenizer.nextToken());
			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;
		System.out.println(ans);
		while(i < jobs) {
			while(i < jobs && used <= ans && arr[i].time <= val + maxdelay) {
				i++;
				used++;
			}
			if(i == jobs) {
				System.out.println(arr[startingindex].pos + " " + arr[i-1].pos + " " + 0);
				break;
			}
			System.out.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++) {
			System.out.println("0");
		}
	}
}

• Subtask 1: 0 / 100