제출 #339615

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
339615		sunshine_unicorn	Job Scheduling (CEOI12_jobs)	Java	0 / 100	165 ms	12628 KiB

jobs

import java.util.*;
import java.io.*;

class scheduling
//public class scheduling
{
   static String[] names;
   public static void main(String[] args) throws FileNotFoundException
   {
      // Scanner in = new Scanner(new File("scheduling.in"));
      Scanner in = new Scanner(System.in);
      int n = in.nextInt();
      int d = in.nextInt();
      int m = in.nextInt();
      Request[] array = new Request[m + 1];
      for(int i = 1; i <= m; i++)
         array[i] = new Request(i, in.nextInt());
      in.close();
      
      array[0] = new Request(-1, -1);
      Arrays.sort(array);
      names = new String[n + 1];
      int result = binarySearch(n, d, m, array);
      works(n, d, m, array, result);
      for(int i = 1; i <= n; i++)
      {
         names[i] += "0 ";
         names[i].trim();
      }
      
      // PrintWriter out = new PrintWriter(new File("scheduling.out"));
      System.out.println(result);
      // out.println(result);
      for(int i = 1; i <= n; i++)
      {
         System.out.println(names[i]);
         // out.println(names[i]);
      }
      // out.close();
   }
   static int binarySearch(int n, int d, int m, Request[] array)
   {
      int a = 1;
      int b = m;
      while(a != b)
      {
         int mid = (a + b) / 2;
         if(works(n, d, m, array, mid))
            b = mid;
         else
            a = mid + 1;
      }
      return a;
   }
   static boolean works(int n, int d, int m, Request[] array, int mid)
   {
      int[] assign = new int[m + 1];
      for(int i = 1; i <= m; i++)
         assign[i] = assign[i - 1] % mid + 1;
      int[] lastSeen = new int[mid + 1];
      for(int i = 1; i <= n; i++)
         names[i] = "";
      
      for(int i = 1; i <= m; i++)
      {
         if(lastSeen[assign[i]] + 1 - array[i].day > d)
            return false;  
         if(array[i].day - lastSeen[assign[i]] > 0)
            lastSeen[assign[i]] = array[i].day;
         else
            lastSeen[assign[i]] = lastSeen[assign[i]] + 1;
         names[lastSeen[assign[i]]] += array[i].index + " ";
      }
      return true;
   }
   static class Request implements Comparable<Request>
   {
      int index, day;
      Request(int index, int day)
      {
         this.index = index;
         this.day = day;
      }
      public int compareTo(Request other)
      {
         return this.day - other.day;
      }
   }
}

• Subtask 1: 0 / 100