Submission #529992

#	Time	Username	Problem	Language	Result	Execution time	Memory
529992		ceoi_mike	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1087 ms	58844 KiB

jobs

import java.util.*;
public class jobs {
    static int N, D, M;
    static ArrayList<Job> jobs;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        jobs = new ArrayList<>();
        N = sc.nextInt();
        D = sc.nextInt();
        M = sc.nextInt();
        for (int i = 0; i < M; i++) {
            int day = sc.nextInt();
            Job j = new Job(day, i+1);
            jobs.add(j);
        }
        Collections.sort(jobs, (Job j1, Job j2) -> Integer.compare (j1.day, j2.day));
        ArrayList<ArrayList<Job>> sched = new ArrayList<>();
        // System.out.println(schedule(sched, 1));
        int n = search(1, 1000001, sched);
        System.out.println(n);
        showSched(sched);
        sc.close();
    }

    static void showSched(ArrayList<ArrayList<Job>> sched) {
        for (int i = 0; i < sched.size(); i++) {
            for (Job j : sched.get(i)) {
                System.out.print(j.id + " ");
            }
            System.out.println("0");
        }
    }

    static boolean schedule(ArrayList<ArrayList<Job>> sched, int nMach) {
        sched.clear();
        for (int i = 0; i < N; i++) {
            sched.add(new ArrayList<>());
        }
        int jobsIdx = 0;
        for (int i = 1; i <= N; i++) {
            // get reference to just this day in sched, call it smaller
            // 
            ArrayList<Job> smaller = sched.get(i-1);
            // 
            // add jobs left

            while (jobsIdx < M && jobs.get(jobsIdx).day <= i && smaller.size() < nMach) {
                smaller.add(new Job(jobs.get(jobsIdx)));
                jobsIdx++;
            }

            // System.out.println(" i: (day): " + i);
            // if (jobsIdx == M) {
            //     System.out.println("stopped because jobsIdx (" + jobsIdx + "equals M " + M);
            // } else {
            //     System.out.println("jobsIdx: " + jobsIdx);
            //     int d = jobs.get(jobsIdx).day;
            //     System.out.println("comparing jobs.get(jobsIdx).day " + d + " to i");
            //     System.out.println("comparing smaller.size (" + smaller.size() + ") to nMach (" + nMach + ")");
            // }
            // System.out.println("--------");
            // this could have terminated  because jobsIdx reached M, because the day
            // of the next job is greater than the current day, or because smaller size
            // reach nMach
            //
            //

            // now check that no jobs in smaller have a day that is past i+D
            for (int j = 0; j < smaller.size(); j++) {
                // day job j was submitted
                // int day_submit = smaller.get(j).day;
                // int time_limit = day_submit + D;
                if (smaller.get(j).day+D < i) return false;
            }
        }
        return true;
    }

    static int search(int lo, int hi, ArrayList<ArrayList<Job>> sched) {
        hi++;
        while (lo < hi) {
            int mid = lo + (hi-lo)/2;
            if (schedule(sched, mid)) {
                hi = mid;
            } else {
                lo = mid+1;
            }
        }
        schedule(sched, lo);
        return lo;
    }

    static class Job {
        public int day;
        public int id;
        public Job(int day, int id) {
            this.day = day;
            this.id = id;
        }
        public Job(Job j) {
            this.day = j.day;
            this.id = j.id;
        }
    }
}

• Subtask 1: 0 / 100