Submission #1300826

#TimeUsernameProblemLanguageResultExecution timeMemory
1300826sz_3312Job Scheduling (CEOI12_jobs)Java
0 / 100
1101 ms120244 KiB
import java.io.*;
import java.util.*;

public class jobs {
    static class Job {
        int day, id;
        Job(int d, int i) { day = d; id = i; }
    }

    static int N, D, M;
    static Job[] jobs;

    // Simple pass to check feasibility
    static boolean works(int K) {
        int ptr = 0;

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

                if (ptr == M) return true;

                if (jobs[ptr].day > day)
                    break;

                if (jobs[ptr].day + D < day)
                    return false;

                ptr++;
            }
        }
        return ptr == M;
    }

    // Build actual schedule once, after minimal K is known
    static List<List<Integer>> buildSchedule(int K) {
        List<List<Integer>> schedule = new ArrayList<>(N);
        for (int i = 0; i < N; i++) schedule.add(new ArrayList<>());

        int ptr = 0;

        for (int day = 1; day <= N; day++) {
            for (int used = 0; used < K; used++) {
                if (ptr == M) return schedule;
                if (jobs[ptr].day > day) break;
                schedule.get(day - 1).add(jobs[ptr].id);
                ptr++;
            }
        }
        return schedule;
    }

    public static void main(String[] args) throws Exception {
        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());

        jobs = new Job[M];

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

        Arrays.sort(jobs, Comparator.comparingInt(a -> a.day));

        int lo = 1, hi = M;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (works(mid)) hi = mid;
            else lo = mid + 1;
        }

        int K = lo;
        List<List<Integer>> schedule = buildSchedule(K);

        StringBuilder out = new StringBuilder();
        out.append(K).append("\n");
        for (int day = 0; day < N; day++) {
            for (int id : schedule.get(day))
                out.append(id).append(" ");
            out.append("0\n");
        }
        System.out.print(out);
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...