Submission #438931

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

        //System.out.println(n);
        //System.exit(0);

        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	1083 ms	22788 KB	Time limit exceeded
2	Execution timed out	1061 ms	22544 KB	Time limit exceeded
3	Execution timed out	1083 ms	22768 KB	Time limit exceeded
4	Execution timed out	1098 ms	22576 KB	Time limit exceeded
5	Execution timed out	1088 ms	22736 KB	Time limit exceeded
6	Execution timed out	1043 ms	22764 KB	Time limit exceeded
7	Execution timed out	1094 ms	22804 KB	Time limit exceeded
8	Execution timed out	1087 ms	22920 KB	Time limit exceeded
9	Execution timed out	1091 ms	21100 KB	Time limit exceeded
10	Execution timed out	1097 ms	21060 KB	Time limit exceeded
11	Execution timed out	1093 ms	20932 KB	Time limit exceeded
12	Execution timed out	1088 ms	25516 KB	Time limit exceeded
13	Execution timed out	1092 ms	28168 KB	Time limit exceeded
14	Execution timed out	1091 ms	33592 KB	Time limit exceeded
15	Execution timed out	1064 ms	36400 KB	Time limit exceeded
16	Execution timed out	1095 ms	37028 KB	Time limit exceeded
17	Execution timed out	1092 ms	37860 KB	Time limit exceeded
18	Execution timed out	1073 ms	36816 KB	Time limit exceeded
19	Execution timed out	1094 ms	38692 KB	Time limit exceeded
20	Execution timed out	1080 ms	36656 KB	Time limit exceeded