Submission #340512

#	Time	Username	Problem	Language	Result	Execution time	Memory
340512		sunshine_unicorn	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1099 ms	55540 KiB

jobs

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

class jobs
//public class jobs
{
   static String[] names;
   public static void main(String[] args) throws FileNotFoundException, IOException
   {
      // Scanner in = new Scanner(new File("jobs.in"));
      // Scanner in = new Scanner(System.in);
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int d = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      Request[] array = new Request[m];
      st = new StringTokenizer(br.readLine());
      for(int i = 0; i < m; i++)
         array[i] = new Request(i + 1, Integer.parseInt(st.nextToken()));
      br.close();
      
      Arrays.sort(array);
      names = new String[n];
      Arrays.fill(names, "");
      int result = binarySearch(n, d, m, array);
      
      int[] lastSeen = new int[result];
      int assign = 0;
      for(int i = 0; i < m; i++)
      {
         if(array[i].day - lastSeen[assign] > 0)
            lastSeen[assign] = array[i].day;
         else
            lastSeen[assign] = lastSeen[assign] + 1;
         names[lastSeen[assign] - 1] += array[i].index + " ";
         assign = (assign + 1) % result;
      }
      
      // PrintWriter out = new PrintWriter(new File("scheduling.out"));
      System.out.println(result);
      // out.println(result);
      for(int i = 0; i < n; i++)
      {
         System.out.println(names[i] + "0");
         // 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[] lastSeen = new int[mid];
      int assign = 0;
      for(int i = 0; i < m; i++)
      {
         if(lastSeen[assign] + 1 - array[i].day > d)
            return false;  
         if(array[i].day - lastSeen[assign] > 0)
            lastSeen[assign] = array[i].day;
         else
            lastSeen[assign] = lastSeen[assign] + 1;
         if(lastSeen[assign] - 1 > n)
            return false;
         assign = (assign + 1) % mid;
      }
      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;
      }
      public String toString()
      {
         return index + ":" + day;
      }
   }
}

• Subtask 1: 0 / 100