Submission #464277

#	Time	Username	Problem	Language	Result	Execution time	Memory
464277		PikaChu999	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1094 ms	54584 KiB

jobs

/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4 
*/
import java.util.*;
import java.io.*;

public class jobs {
  public static long numDays;
  public static long maxDelay; 
  public static int numRequests;
  public static Request[] requests;
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer details = new StringTokenizer(br.readLine());
    numDays = Long.parseLong(details.nextToken());
    maxDelay = Long.parseLong(details.nextToken());
    numRequests = Integer.parseInt(details.nextToken());

    requests = new Request[numRequests];
    StringTokenizer r = new StringTokenizer(br.readLine());
    for(int x = 0; x < numRequests; x++) requests[x] = new Request(x, Long.parseLong(r.nextToken()));
    Arrays.sort(requests);
    //System.out.println(Arrays.toString(requests));

    //output is formatted by requests + " " + 0
    long min = 0;
    long max = 10000000;

    while(min < max){
      long mid = (min + max)/2;
      if(works(mid)){
        max = mid;
      }
      else min = mid + 1;
    }

    generate(max);

    br.close();
  }
  public static boolean works(long numMachines){
    PriorityQueue<Request> delayed = new PriorityQueue<Request>();
    long currentDay = 0;
    int requestInd = 0;
    long available = numMachines;
    while(currentDay <= numDays){
      //System.out.println(currentDay + " " + delayed + " " + requestInd);
      //even on days where there are no new requests one can work on the delayed ones
      available = numMachines; 
      while(!delayed.isEmpty() && available > 0){
        available--; 
        Request cur = delayed.poll();
        if(currentDay - cur.day > maxDelay) return false; 
      }
      while(requestInd < numRequests && requests[requestInd].day == currentDay){
        if(available > 0){
          available--;
          requestInd++;
        }
        else{
          delayed.add(requests[requestInd]);
          requestInd++;
        }
      }
      currentDay++;
    }
    return requestInd >= numRequests - 1;
  }
  public static void generate(long numMachines){
    System.out.println(numMachines);
    PriorityQueue<Request> delayed = new PriorityQueue<Request>();
    long currentDay = 0;
    int requestInd = 0;
    long available = numMachines;
    while(currentDay <= numDays){
      //System.out.println(currentDay + " " + delayed + " " + requestInd);
      //even on days where there are no new requests one can work on the delayed ones
      ArrayList<Request> processed = new ArrayList<Request>();
      available = numMachines; 
      while(!delayed.isEmpty() && available > 0){
        available--; 
        processed.add(delayed.poll());
      }
      while(requestInd < numRequests && requests[requestInd].day == currentDay){
        if(available > 0){
          available--;
          processed.add(requests[requestInd]);
          requestInd++;
        }
        else{
          delayed.add(requests[requestInd]);
          requestInd++;
        }
      }
      currentDay++;
      String ret = "";
      for(Request r : processed) ret += r.toString() + " ";
      System.out.println(ret + "0");
    }
  }
}
class Request implements Comparable<Request>{
  long day; 
  int id; 
  public Request(int i, long d){
    day = d;
    id = i;
  }
  public int compareTo(Request r){
    if(r.day < day) return 1;
    else if(r.day > day) return -1;
    return id - r.id;
  }
  public String toString(){
    return String.valueOf(id);
  }
}

• Subtask 1: 0 / 100