Submission #438981

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
438981	2021-06-29T02:45:46 Z	Airy	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	37876 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) {
        return true;
        /*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	Runtime error	756 ms	20664 KB	Execution failed because the return code was nonzero
2	Runtime error	758 ms	20916 KB	Execution failed because the return code was nonzero
3	Runtime error	734 ms	20620 KB	Execution failed because the return code was nonzero
4	Runtime error	732 ms	20664 KB	Execution failed because the return code was nonzero
5	Runtime error	725 ms	20708 KB	Execution failed because the return code was nonzero
6	Runtime error	733 ms	20656 KB	Execution failed because the return code was nonzero
7	Runtime error	707 ms	20516 KB	Execution failed because the return code was nonzero
8	Runtime error	715 ms	20664 KB	Execution failed because the return code was nonzero
9	Execution timed out	1079 ms	21024 KB	Time limit exceeded
10	Execution timed out	1050 ms	20872 KB	Time limit exceeded
11	Execution timed out	1057 ms	20768 KB	Time limit exceeded
12	Execution timed out	1083 ms	25608 KB	Time limit exceeded
13	Execution timed out	1080 ms	28024 KB	Time limit exceeded
14	Execution timed out	1020 ms	32556 KB	Time limit exceeded
15	Execution timed out	1091 ms	36368 KB	Time limit exceeded
16	Execution timed out	1083 ms	36268 KB	Time limit exceeded
17	Execution timed out	1093 ms	37360 KB	Time limit exceeded
18	Execution timed out	1103 ms	37324 KB	Time limit exceeded
19	Execution timed out	1079 ms	37876 KB	Time limit exceeded
20	Execution timed out	1101 ms	36384 KB	Time limit exceeded