Submission #340489

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
340489	2020-12-27T17:53:56 Z	sunshine_unicorn	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	46484 KB

jobs

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

class jobs
//public class jobs
{
   static String[] names;
   public static void main(String[] args) throws FileNotFoundException
   {
      // Scanner in = new Scanner(new File("jobs.in"));
      Scanner in = new Scanner(System.in);
      int n = in.nextInt();
      int d = in.nextInt();
      int m = in.nextInt();
      Request[] array = new Request[m];
      for(int i = 0; i < m; i++)
         array[i] = new Request(i + 1, in.nextInt());
      in.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	1034 ms	23380 KB	Time limit exceeded
2	Execution timed out	1070 ms	22580 KB	Time limit exceeded
3	Execution timed out	1075 ms	22440 KB	Time limit exceeded
4	Execution timed out	1086 ms	22440 KB	Time limit exceeded
5	Execution timed out	1080 ms	22520 KB	Time limit exceeded
6	Execution timed out	1099 ms	22548 KB	Time limit exceeded
7	Execution timed out	1092 ms	22592 KB	Time limit exceeded
8	Execution timed out	1098 ms	22440 KB	Time limit exceeded
9	Execution timed out	1091 ms	21636 KB	Time limit exceeded
10	Execution timed out	1095 ms	21748 KB	Time limit exceeded
11	Execution timed out	1080 ms	21524 KB	Time limit exceeded
12	Execution timed out	1059 ms	26676 KB	Time limit exceeded
13	Execution timed out	1047 ms	29892 KB	Time limit exceeded
14	Execution timed out	1100 ms	36160 KB	Time limit exceeded
15	Execution timed out	1084 ms	38524 KB	Time limit exceeded
16	Execution timed out	1053 ms	39452 KB	Time limit exceeded
17	Execution timed out	1101 ms	41400 KB	Time limit exceeded
18	Execution timed out	1098 ms	45152 KB	Time limit exceeded
19	Execution timed out	1095 ms	46484 KB	Time limit exceeded
20	Execution timed out	1099 ms	41344 KB	Time limit exceeded