Submission #340490

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
340490	2020-12-27T18:06:51 Z	sunshine_unicorn	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	55300 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];
      int result = binarySearch(n, d, m, array);
      works(n, d, m, array, 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[] assign = new int[m];
      for(int i = 1; i < m; i++)
         assign[i] = (assign[i - 1] + 1) % mid;
      int[] lastSeen = new int[mid];
      for(int i = 0; i < n; i++)
         names[i] = "";
      
      for(int i = 0; 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;
         if(lastSeen[assign[i]] - 1 > n)
            return false;
         names[lastSeen[assign[i]] - 1] += 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;
      }
      public String toString()
      {
         return index + ":" + day;
      }
   }
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1084 ms	19848 KB	Time limit exceeded
2	Execution timed out	1088 ms	19884 KB	Time limit exceeded
3	Execution timed out	1076 ms	20140 KB	Time limit exceeded
4	Execution timed out	1084 ms	19992 KB	Time limit exceeded
5	Execution timed out	1032 ms	20120 KB	Time limit exceeded
6	Execution timed out	1090 ms	20012 KB	Time limit exceeded
7	Execution timed out	1027 ms	19756 KB	Time limit exceeded
8	Execution timed out	1095 ms	19912 KB	Time limit exceeded
9	Execution timed out	1088 ms	18180 KB	Time limit exceeded
10	Execution timed out	1095 ms	18312 KB	Time limit exceeded
11	Execution timed out	1049 ms	18492 KB	Time limit exceeded
12	Execution timed out	1095 ms	21720 KB	Time limit exceeded
13	Execution timed out	1074 ms	25784 KB	Time limit exceeded
14	Execution timed out	1076 ms	31116 KB	Time limit exceeded
15	Execution timed out	1092 ms	36408 KB	Time limit exceeded
16	Execution timed out	1103 ms	42160 KB	Time limit exceeded
17	Execution timed out	1097 ms	44860 KB	Time limit exceeded
18	Execution timed out	1051 ms	47128 KB	Time limit exceeded
19	Execution timed out	1103 ms	55300 KB	Time limit exceeded
20	Execution timed out	1058 ms	44628 KB	Time limit exceeded