Submission #438923

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
438923	2021-06-29T00:01:25 Z	Airy	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	38572 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;

        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	1086 ms	22664 KB	Time limit exceeded
2	Execution timed out	1098 ms	22696 KB	Time limit exceeded
3	Execution timed out	1079 ms	22824 KB	Time limit exceeded
4	Execution timed out	1083 ms	22760 KB	Time limit exceeded
5	Execution timed out	1084 ms	22860 KB	Time limit exceeded
6	Execution timed out	1085 ms	22660 KB	Time limit exceeded
7	Execution timed out	1094 ms	22716 KB	Time limit exceeded
8	Execution timed out	1097 ms	22948 KB	Time limit exceeded
9	Execution timed out	1090 ms	21012 KB	Time limit exceeded
10	Execution timed out	1090 ms	21072 KB	Time limit exceeded
11	Execution timed out	1086 ms	20876 KB	Time limit exceeded
12	Execution timed out	1094 ms	25252 KB	Time limit exceeded
13	Execution timed out	1086 ms	28240 KB	Time limit exceeded
14	Execution timed out	1100 ms	33616 KB	Time limit exceeded
15	Execution timed out	1085 ms	35912 KB	Time limit exceeded
16	Execution timed out	1097 ms	36064 KB	Time limit exceeded
17	Execution timed out	1096 ms	36924 KB	Time limit exceeded
18	Execution timed out	1092 ms	38572 KB	Time limit exceeded
19	Execution timed out	1082 ms	38128 KB	Time limit exceeded
20	Execution timed out	1096 ms	36644 KB	Time limit exceeded