oj.uz

Submission #492232

# Submission time Handle Problem Language Result Execution time Memory
492232 2021-12-06T02:54:36 Z surikabir Job Scheduling (CEOI12_jobs) Java 11
5 / 100
 1000 ms 61492 KB 
import java.util.*;
import java.io.*;
public class jobs{
   public static int N;
   public static int D;
   public static int M;
   public static ArrayList<Integer>[] arrOfList;
   public static void main(String[] args) throws IOException{
      BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer s=new StringTokenizer(br.readLine());
      N=Integer.parseInt(s.nextToken());
      D=Integer.parseInt(s.nextToken());
      M=Integer.parseInt(s.nextToken());
      arrOfList=new ArrayList[N+1];
      for(int i=1;i<=N;i++){
         arrOfList[i]=new ArrayList<Integer>();
      }
      s=new StringTokenizer(br.readLine());
      for(int i=1;i<=M;i++){
         arrOfList[Integer.parseInt(s.nextToken())].add(i);
      }
      int a = 0, b = N-1;
      while (a != b) {
         int mid = (a+b)/2;
         if (works(mid)) {
            b = mid;
         }
         else {
            a = mid+1;
         }
      }
      print(a);
   }
   public static boolean works(int machines){
      Queue<Integer> orders=new LinkedList<Integer>();
      for(int i=1;i<=N;i++){
         for(int k=0;k<arrOfList[i].size();k++){
            orders.add(i);
         }
         for(int k=0;k<machines&&!orders.isEmpty();k++){
            int day=orders.remove();
            if(day<i-D)return false;
         }
      }
      return orders.isEmpty();
   }
   public static void print(int machines){
      System.out.println(machines);
      Queue<Integer> orders=new LinkedList<Integer>();
      for(int i=1;i<=N;i++){
         for(int k=0;k<arrOfList[i].size();k++){
            orders.add(arrOfList[i].get(k));
         }
         for(int k=0;k<machines&&!orders.isEmpty();k++){
            System.out.print(orders.remove()+" ");
         }
         System.out.println(0);
      }
   }
}

Compilation message

Note: jobs.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Subtask #1
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1056 ms 26496 KB Time limit exceeded
2 Execution timed out 1067 ms 26188 KB Time limit exceeded
3 Execution timed out 1030 ms 26304 KB Time limit exceeded
4 Execution timed out 1088 ms 26224 KB Time limit exceeded
5 Execution timed out 1057 ms 26432 KB Time limit exceeded
6 Execution timed out 1051 ms 26124 KB Time limit exceeded
7 Execution timed out 1083 ms 26164 KB Time limit exceeded
8 Execution timed out 1060 ms 26260 KB Time limit exceeded
9 Execution timed out 1089 ms 27120 KB Time limit exceeded
10 Execution timed out 1091 ms 27004 KB Time limit exceeded
11 Correct 944 ms 18672 KB Output is correct
12 Execution timed out 1087 ms 25852 KB Time limit exceeded
13 Execution timed out 1092 ms 28724 KB Time limit exceeded
14 Execution timed out 1092 ms 37808 KB Time limit exceeded
15 Execution timed out 1094 ms 36192 KB Time limit exceeded
16 Execution timed out 1082 ms 43936 KB Time limit exceeded
17 Execution timed out 1080 ms 48416 KB Time limit exceeded
18 Execution timed out 1037 ms 49740 KB Time limit exceeded
19 Execution timed out 1087 ms 61492 KB Time limit exceeded
20 Execution timed out 1079 ms 48436 KB Time limit exceeded