Submission #1138439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138439		mrsmartypants	Job Scheduling (CEOI12_jobs)	Java	40 / 100	1099 ms	103340 KiB

jobs

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

public class jobs {

    static ArrayList<ArrayList<Integer>> schedule = new ArrayList<>();
    static int N, D, M;

    static int[][] jobs;

    public static void main(String... args) throws IOException {

//        BufferedReader reader = new BufferedReader(new FileReader("input.in"));
        BufferedReader reader = new BufferedReader(new InputStreamReader(new DataInputStream(System.in)));

        PrintWriter writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

        StringTokenizer st = new StringTokenizer(reader.readLine());
        N = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(reader.readLine());
        jobs = new int[M][];
        for (int i = 0; i < M; i++) {
            jobs[i] = new int[] {i + 1, Integer.parseInt(st.nextToken())};
        }

        Arrays.sort(jobs, Comparator.comparingInt(j -> j[1]));

//        System.out.println(Arrays.toString(jobs));
        int lo = 1;
        int hi = M;

        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;



            if (test(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }

        }

        writer.println(lo);
        int reqNum = 0;
        o: for (int day = 1; day <= N; day++) {

            schedule.add(new ArrayList<>());
            for (int j = 0; j < lo; j++) {


                if (jobs[reqNum][1] > day) break;


                if (jobs[reqNum][1] + D >= day) {
                    schedule.get(day - 1).add(jobs[reqNum][0]);
                    reqNum++;
                }

                if (reqNum == M) break o;
            }
        }

        while (schedule.size() < N) schedule.add(new ArrayList<>());

        for (ArrayList<Integer> ds : schedule) {
            for (int z : ds) {
                writer.print(z + " ");
            }
            writer.println(0);
        }

        writer.close();


    }

    static boolean test(int numMachines) {

        int reqNum = 0;

        for (int day = 1; day <= N; day++) {

            for (int j = 0; j < numMachines; j++) {


                if (jobs[reqNum][1] > day) break;


                if (jobs[reqNum][1] + D >= day) {

                    reqNum++;
                } else {
                    return false;
                }

                if (reqNum == M) return true;
            }
        }

        return false;
    }

}

• Subtask 1: 40 / 100