Submission #354457

#	Time	Username	Problem	Language	Result	Execution time	Memory
354457		superadi04	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1097 ms	39472 KiB

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