Submission #438926

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
438926	2021-06-29T00:05:20 Z	Airy	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	38512 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	Incorrect	793 ms	21952 KB	Output isn't correct
2	Incorrect	789 ms	21996 KB	Output isn't correct
3	Incorrect	746 ms	21936 KB	Output isn't correct
4	Incorrect	725 ms	22004 KB	Output isn't correct
5	Incorrect	730 ms	22144 KB	Output isn't correct
6	Incorrect	722 ms	22048 KB	Output isn't correct
7	Incorrect	742 ms	21924 KB	Output isn't correct
8	Incorrect	737 ms	22160 KB	Output isn't correct
9	Execution timed out	1078 ms	20924 KB	Time limit exceeded
10	Execution timed out	1088 ms	21004 KB	Time limit exceeded
11	Execution timed out	1099 ms	20832 KB	Time limit exceeded
12	Execution timed out	1090 ms	25356 KB	Time limit exceeded
13	Execution timed out	1088 ms	28240 KB	Time limit exceeded
14	Execution timed out	1087 ms	33720 KB	Time limit exceeded
15	Execution timed out	1090 ms	36412 KB	Time limit exceeded
16	Execution timed out	1076 ms	36592 KB	Time limit exceeded
17	Execution timed out	1084 ms	37356 KB	Time limit exceeded
18	Execution timed out	1079 ms	37284 KB	Time limit exceeded
19	Execution timed out	1093 ms	38512 KB	Time limit exceeded
20	Execution timed out	1091 ms	37136 KB	Time limit exceeded