Submission #438990

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
438990	2021-06-29T03:16:50 Z	Airy	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	37172 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	Incorrect	782 ms	21980 KB	Output isn't correct
2	Incorrect	757 ms	22032 KB	Output isn't correct
3	Incorrect	781 ms	22476 KB	Output isn't correct
4	Incorrect	779 ms	22348 KB	Output isn't correct
5	Incorrect	829 ms	21856 KB	Output isn't correct
6	Incorrect	791 ms	22072 KB	Output isn't correct
7	Incorrect	750 ms	22372 KB	Output isn't correct
8	Incorrect	803 ms	22032 KB	Output isn't correct
9	Execution timed out	1076 ms	21172 KB	Time limit exceeded
10	Execution timed out	1094 ms	20756 KB	Time limit exceeded
11	Execution timed out	1065 ms	20744 KB	Time limit exceeded
12	Execution timed out	1082 ms	25324 KB	Time limit exceeded
13	Execution timed out	1061 ms	28108 KB	Time limit exceeded
14	Execution timed out	1089 ms	33600 KB	Time limit exceeded
15	Execution timed out	1089 ms	35588 KB	Time limit exceeded
16	Execution timed out	1085 ms	34636 KB	Time limit exceeded
17	Execution timed out	1085 ms	34864 KB	Time limit exceeded
18	Execution timed out	1088 ms	36316 KB	Time limit exceeded
19	Execution timed out	1075 ms	37172 KB	Time limit exceeded
20	Execution timed out	1093 ms	36476 KB	Time limit exceeded