Submission #354455

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
354455	2021-01-22T02:06:24 Z	superadi04	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	58272 KB

jobs

import java.io.*;
import java.util.*;

public class jobs {
    static int n, d, m;
    static Pair[] requests;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        requests = new Pair[m];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            requests[i] = new Pair(Integer.parseInt(st.nextToken()), i + 1);
        }
        Arrays.sort(requests, (r1, r2) -> r1.a - r2.a);

        // Binary search on the answer
        int lo = 0, hi = n;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (check(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }

        // Print answer
        System.out.println(lo);
        int days = 0;
        for (int i = 0; i < m; i += lo) {
            days++;
            int j = i;
            while (j < m && j < i + lo) {
                System.out.print(requests[j].b + " ");
                j++;
            }
            System.out.println(0);
        }

        // Print out the remaining zeroes
        while (days < n) {
            days++;
            System.out.println(0);
        }
    }


    static boolean check(int delay) {
        int days = 0;
        for (int i = 0; i < m; i += delay) {
            days++;
            int j = i;
            while (j < m && j < i + delay) {
                if (requests[j].a + d >= days) {
                    j++;
                } else {
                    return false;
                }
            }
        }
        return days <= n;
    }

    static class Pair {
        int a, b;

        public Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1089 ms	20368 KB	Time limit exceeded
2	Execution timed out	1047 ms	19932 KB	Time limit exceeded
3	Execution timed out	1088 ms	20044 KB	Time limit exceeded
4	Execution timed out	1096 ms	20064 KB	Time limit exceeded
5	Execution timed out	1089 ms	20040 KB	Time limit exceeded
6	Execution timed out	1084 ms	20100 KB	Time limit exceeded
7	Execution timed out	1085 ms	20192 KB	Time limit exceeded
8	Execution timed out	1059 ms	19828 KB	Time limit exceeded
9	Execution timed out	1100 ms	19888 KB	Time limit exceeded
10	Execution timed out	1051 ms	20236 KB	Time limit exceeded
11	Execution timed out	1088 ms	20936 KB	Time limit exceeded
12	Execution timed out	1092 ms	24084 KB	Time limit exceeded
13	Execution timed out	1091 ms	28312 KB	Time limit exceeded
14	Execution timed out	1095 ms	34488 KB	Time limit exceeded
15	Execution timed out	1093 ms	40104 KB	Time limit exceeded
16	Execution timed out	1098 ms	46352 KB	Time limit exceeded
17	Execution timed out	1094 ms	49516 KB	Time limit exceeded
18	Execution timed out	1076 ms	51220 KB	Time limit exceeded
19	Execution timed out	1083 ms	58272 KB	Time limit exceeded
20	Execution timed out	1067 ms	49260 KB	Time limit exceeded