Submission #438919

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
438919	2021-06-28T23:59:05 Z	Airy	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	40432 KB

jobs

import java.util.*;
 
class jobs {
    public static Pair [] arr;
    public static int m;
    public static int d;
    public static int n;
    public static int [] times;
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
 
        n = s.nextInt();
        d = s.nextInt();
        m = s.nextInt();
 
        arr = new Pair [m];
 
        for (int i = 0; i < m; i++) {
            arr[i] = new Pair (s.nextInt(), i + 1);
        }
 
        Arrays.sort(arr);
 
        int a = 1, b = m;
        int mid = 1;
        
        while (a != b) {
            mid = (a + b) / 2;
 
            if (simulate(mid)) {
                b = mid;
            }
 
            else {
                a = mid + 1;
            }
        }
 
        if (!simulate(mid)) {
            simulate(mid + 1);
            mid++;
            System.out.println(mid);
        }
 
        else {
            simulate(mid);
            System.out.println(mid);
        }
 
        int pos = 0;
        int dayf = 1;
        boolean done = false;
      
      	System.out.println("here");
 
        for (int i = 0; i < n; i++) {
            //System.out.println(pos + mid + "h" + done);
            if (done) {
                System.out.println(0);
                continue;
            }
 
            if ((pos + mid) >= m) {
                done = true;
            }
 
            for (int j = pos; j < m; j++) {
                //System.out.println(j + " " + dayf + " " + times[j]);
                if (!(dayf == times[j])) {
                    dayf++;
                    pos = j;
                    break;
                }
 
                System.out.print(arr[j].index + " ");
            }
 
            System.out.print(0);
 
            System.out.println();
        }
    }
 
    public static boolean simulate (int x) {
        int counter = 1;
        int day = 1;
 
        times = new int [m];
 
        for (int i = 0; i < m; i++) {
            times[i] = day;
 
            counter++;
 
            if (counter > x) {
                counter = 1;
                day++;
            }
        }
 
        //System.out.println(Arrays.toString(times) + " " + x);
 
        for (int i = 0; i < m; i++) {
            if (times[i] - arr[i].sorter > d) {
                return false;
            }
        }
 
        return true;
    }
 
    private static class Pair implements Comparable<Pair> {
        int sorter;
        int index;
 
        public Pair(int location, int index) {
            this.sorter = location;
            this.index = index;
        }
        
        @Override
        public int compareTo(Pair o) {
            return sorter - o.sorter;
        }
 
        @Override
        public boolean equals (Object other) {
            Pair nother = (Pair) other;
            return nother.sorter == sorter;
        }
    }
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1093 ms	23408 KB	Time limit exceeded
2	Execution timed out	1073 ms	22892 KB	Time limit exceeded
3	Execution timed out	1083 ms	23132 KB	Time limit exceeded
4	Execution timed out	1086 ms	23012 KB	Time limit exceeded
5	Execution timed out	1085 ms	23156 KB	Time limit exceeded
6	Execution timed out	1093 ms	23072 KB	Time limit exceeded
7	Execution timed out	1073 ms	22892 KB	Time limit exceeded
8	Execution timed out	1064 ms	23072 KB	Time limit exceeded
9	Execution timed out	1092 ms	21412 KB	Time limit exceeded
10	Execution timed out	1092 ms	21280 KB	Time limit exceeded
11	Execution timed out	1082 ms	21312 KB	Time limit exceeded
12	Execution timed out	1085 ms	26148 KB	Time limit exceeded
13	Execution timed out	1087 ms	29332 KB	Time limit exceeded
14	Execution timed out	1083 ms	35764 KB	Time limit exceeded
15	Execution timed out	1064 ms	37340 KB	Time limit exceeded
16	Execution timed out	1077 ms	38316 KB	Time limit exceeded
17	Execution timed out	1085 ms	38188 KB	Time limit exceeded
18	Execution timed out	1089 ms	39400 KB	Time limit exceeded
19	Execution timed out	1090 ms	40432 KB	Time limit exceeded
20	Execution timed out	1095 ms	38212 KB	Time limit exceeded