Submission #1300825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300825		sz_3312	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1101 ms	131072 KiB

jobs

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;

    // Try using K machines. If feasible, return schedule; else return null.
    static List<List<Integer>> feasible(int K) {
        List<List<Integer>> schedule = new ArrayList<>();
        for (int i = 0; i < N; i++) schedule.add(new ArrayList<>());

        int ptr = 0; // pointer into sorted jobs

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

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

                if (ptr == M) 
                    return schedule; // all jobs scheduled

                // if next job's arrival day is > this day, we can't schedule more today
                if (jobs[ptr].day > day)
                    break;

                // deadline check
                if (jobs[ptr].day + D < day)
                    return null; // missed deadline → infeasible

                // schedule this job on this day
                schedule.get(day - 1).add(jobs[ptr].id);
                ptr++;
            }
        }

        if (ptr < M) 
            return null; // some jobs not scheduled → fail

        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;
        List<List<Integer>> answerSchedule = null;

        while (lo < hi) {
            int mid = (lo + hi) / 2;
            List<List<Integer>> test = feasible(mid);
            if (test != null) {
                hi = mid;
                answerSchedule = test;
            } else {
                lo = mid + 1;
            }
        }

        // final check with lo machines
        if (answerSchedule == null)
            answerSchedule = feasible(lo);

        StringBuilder out = new StringBuilder();
        out.append(lo).append("\n");
        for (int day = 0; day < N; day++) {
            for (int id : answerSchedule.get(day))
                out.append(id).append(" ");
            out.append(0).append("\n");
        }
        System.out.println(out);
    }
}

• Subtask 1: 0 / 100