Submission #492232

#	Time	Username	Problem	Language	Result	Execution time	Memory
492232		surikabir	Job Scheduling (CEOI12_jobs)	Java	5 / 100	1094 ms	61492 KiB

jobs

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 (stderr)

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

• Subtask 1: 5 / 100