Submission #354457

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
354457	2021-01-22T02:12:43 Z	superadi04	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	39472 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 Exception {
        FastIO fi = new FastIO(System.in);
        n = fi.nextInt();
        d = fi.nextInt();
        m = fi.nextInt();
        requests = new Pair[m];
        for (int i = 0; i < m; i++) {
            requests[i] = new Pair(fi.nextInt(), 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;
        }
    }

    static class FastIO {

        InputStream dis;
        byte[] buffer = new byte[1 << 17];
        int pointer = 0;

        public FastIO(String fileName) throws Exception {
            dis = new FileInputStream(fileName);
        }

        public FastIO(InputStream is) throws Exception {
            dis = is;
        }

        int nextInt() throws Exception {
            int ret = 0;

            byte b;
            do {
                b = nextByte();
            } while (b <= ' ');
            boolean negative = false;
            if (b == '-') {
                negative = true;
                b = nextByte();
            }
            while (b >= '0' && b <= '9') {
                ret = 10 * ret + b - '0';
                b = nextByte();
            }

            return (negative) ? -ret : ret;
        }

        long nextLong() throws Exception {
            long ret = 0;

            byte b;
            do {
                b = nextByte();
            } while (b <= ' ');
            boolean negative = false;
            if (b == '-') {
                negative = true;
                b = nextByte();
            }
            while (b >= '0' && b <= '9') {
                ret = 10 * ret + b - '0';
                b = nextByte();
            }

            return (negative) ? -ret : ret;
        }

        byte nextByte() throws Exception {
            if (pointer == buffer.length) {
                dis.read(buffer, 0, buffer.length);
                pointer = 0;
            }
            return buffer[pointer++];
        }

        String next() throws Exception {
            StringBuffer ret = new StringBuffer();

            byte b;
            do {
                b = nextByte();
            } while (b <= ' ');
            while (b > ' ') {
                ret.appendCodePoint(b);
                b = nextByte();
            }

            return ret.toString();
        }

    }
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1079 ms	18096 KB	Time limit exceeded
2	Execution timed out	1081 ms	18136 KB	Time limit exceeded
3	Execution timed out	1089 ms	18024 KB	Time limit exceeded
4	Execution timed out	1074 ms	18192 KB	Time limit exceeded
5	Execution timed out	1086 ms	18332 KB	Time limit exceeded
6	Execution timed out	1084 ms	18296 KB	Time limit exceeded
7	Execution timed out	1078 ms	18292 KB	Time limit exceeded
8	Execution timed out	1080 ms	18364 KB	Time limit exceeded
9	Execution timed out	1091 ms	17660 KB	Time limit exceeded
10	Execution timed out	1095 ms	17584 KB	Time limit exceeded
11	Execution timed out	1097 ms	18204 KB	Time limit exceeded
12	Execution timed out	1050 ms	22336 KB	Time limit exceeded
13	Execution timed out	1048 ms	22816 KB	Time limit exceeded
14	Execution timed out	1081 ms	30012 KB	Time limit exceeded
15	Execution timed out	1078 ms	30208 KB	Time limit exceeded
16	Execution timed out	1048 ms	33580 KB	Time limit exceeded
17	Execution timed out	1058 ms	34560 KB	Time limit exceeded
18	Execution timed out	1081 ms	37036 KB	Time limit exceeded
19	Execution timed out	1070 ms	39472 KB	Time limit exceeded
20	Execution timed out	1056 ms	34552 KB	Time limit exceeded