Submission #424155

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
424155	2021-06-11T17:23:37 Z	PikaChu999	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	57136 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1080 ms	20044 KB	Time limit exceeded
2	Execution timed out	1060 ms	19964 KB	Time limit exceeded
3	Execution timed out	1081 ms	19496 KB	Time limit exceeded
4	Execution timed out	1095 ms	19448 KB	Time limit exceeded
5	Execution timed out	1075 ms	19664 KB	Time limit exceeded
6	Execution timed out	1020 ms	19712 KB	Time limit exceeded
7	Execution timed out	1083 ms	19780 KB	Time limit exceeded
8	Execution timed out	1063 ms	19756 KB	Time limit exceeded
9	Execution timed out	1057 ms	17744 KB	Time limit exceeded
10	Execution timed out	1094 ms	17848 KB	Time limit exceeded
11	Execution timed out	1083 ms	18036 KB	Time limit exceeded
12	Execution timed out	1093 ms	22136 KB	Time limit exceeded
13	Execution timed out	1083 ms	26356 KB	Time limit exceeded
14	Execution timed out	1082 ms	32284 KB	Time limit exceeded
15	Execution timed out	1092 ms	38040 KB	Time limit exceeded
16	Execution timed out	1066 ms	44356 KB	Time limit exceeded
17	Execution timed out	1087 ms	47388 KB	Time limit exceeded
18	Execution timed out	1095 ms	49060 KB	Time limit exceeded
19	Execution timed out	1087 ms	57136 KB	Time limit exceeded
20	Execution timed out	1093 ms	47204 KB	Time limit exceeded