Submission #340512

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
340512	2020-12-27T19:30:58 Z	sunshine_unicorn	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	55540 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1070 ms	20444 KB	Time limit exceeded
2	Execution timed out	1069 ms	19808 KB	Time limit exceeded
3	Execution timed out	1088 ms	19992 KB	Time limit exceeded
4	Execution timed out	1083 ms	19892 KB	Time limit exceeded
5	Execution timed out	1081 ms	19880 KB	Time limit exceeded
6	Execution timed out	1083 ms	19992 KB	Time limit exceeded
7	Execution timed out	1089 ms	19840 KB	Time limit exceeded
8	Execution timed out	1085 ms	19904 KB	Time limit exceeded
9	Execution timed out	1087 ms	18500 KB	Time limit exceeded
10	Execution timed out	1090 ms	18212 KB	Time limit exceeded
11	Execution timed out	1096 ms	19040 KB	Time limit exceeded
12	Execution timed out	1094 ms	22516 KB	Time limit exceeded
13	Execution timed out	1099 ms	26464 KB	Time limit exceeded
14	Execution timed out	1087 ms	31728 KB	Time limit exceeded
15	Execution timed out	1091 ms	37320 KB	Time limit exceeded
16	Execution timed out	1097 ms	42900 KB	Time limit exceeded
17	Execution timed out	1057 ms	45556 KB	Time limit exceeded
18	Execution timed out	1086 ms	48068 KB	Time limit exceeded
19	Execution timed out	1098 ms	55540 KB	Time limit exceeded
20	Execution timed out	1088 ms	45560 KB	Time limit exceeded