Submission #474786

#	Time	Username	Problem	Language	Result	Execution time	Memory
474786		sbane13	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1100 ms	43180 KiB

jobs

import java.util.*;

public class jobs {

    static int n, d, m;

    static ArrayList<Job> jobs = new ArrayList<>();

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);

        n = in.nextInt(); d = in.nextInt(); m = in.nextInt();


        for(int i = 0; i < m; i++){
            jobs.add(new Job(in.nextInt(), i));
        }

        Collections.sort(jobs);

        int s = 1, e = 1000000000;

        while (s != e) {
            int mid = (s+e)/2;
            if (is_pos(mid)) {
                e = mid;
            } else {
                s = mid + 1;
            }
        }

        int ans = s;

        System.out.println(ans);

        int i = 0, j = 0;

        for (int day = 1; day <= n; day++) {
            while (j < jobs.size() && j - i + 1 <= ans && jobs.get(j).job <= day) {
                j++;
            }
            while (i < j) {
                System.out.print(jobs.get(i).day + 1 + " ");
                i++;
            }

            System.out.println("0");

        }
    }

    static boolean is_pos(int mid) {
        int i = 0, j = 0;

        for (int day = 1; day <= n; day++) {
            while (j < jobs.size() && j - i + 1 <= mid && jobs.get(j).job <= day) {
                j++;
            }
            while (i < j) {
                if (day - jobs.get(i).job > d) return false;
                i++;
            }
        }

        return i >= n;
    }

    static class Job implements Comparable<Job>{
        int job, day;

        public Job(int job, int day) {
            this.job = job;
            this.day = day;
        }

        public int compareTo(Job o) {
            return this.job-o.job;
        }
    }
}

• Subtask 1: 0 / 100