Submission #464277

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
464277	2021-08-12T16:49:05 Z	PikaChu999	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	54584 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	1083 ms	19832 KB	Time limit exceeded
2	Execution timed out	1080 ms	19808 KB	Time limit exceeded
3	Execution timed out	1078 ms	19632 KB	Time limit exceeded
4	Execution timed out	1070 ms	19792 KB	Time limit exceeded
5	Execution timed out	1070 ms	19588 KB	Time limit exceeded
6	Execution timed out	1028 ms	19444 KB	Time limit exceeded
7	Execution timed out	1091 ms	19612 KB	Time limit exceeded
8	Execution timed out	1082 ms	19620 KB	Time limit exceeded
9	Execution timed out	1092 ms	17864 KB	Time limit exceeded
10	Execution timed out	1089 ms	17796 KB	Time limit exceeded
11	Execution timed out	1087 ms	18224 KB	Time limit exceeded
12	Execution timed out	1087 ms	21872 KB	Time limit exceeded
13	Execution timed out	1094 ms	25864 KB	Time limit exceeded
14	Execution timed out	1078 ms	31292 KB	Time limit exceeded
15	Execution timed out	1077 ms	36992 KB	Time limit exceeded
16	Execution timed out	1083 ms	42328 KB	Time limit exceeded
17	Execution timed out	1076 ms	45120 KB	Time limit exceeded
18	Execution timed out	1038 ms	46712 KB	Time limit exceeded
19	Execution timed out	1042 ms	54584 KB	Time limit exceeded
20	Execution timed out	1081 ms	44736 KB	Time limit exceeded