Submission #513274

#	Time	Username	Problem	Language	Result	Execution time	Memory
513274		ryankim0709	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1093 ms	53608 KiB

jobs

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

public class jobs {
    static class Job implements Comparable<Job> {
        int index;
        int day;

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

        public int compareTo(Job a) {
            return this.day - a.day;
        }
    }

    static int N, D, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); // # of days organization works
        D = Integer.parseInt(st.nextToken()); // Maximum permitted delay
        M = Integer.parseInt(st.nextToken()); // # of job requests

        Job[] jobs = new Job[M];

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

        Arrays.sort(jobs);

        int lo = 1;
        int hi = M + 1;

        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (simulate(mid, jobs)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }

        System.out.println(hi);
        System.out.println(getAnswer(hi, jobs));
    }

    public static String getAnswer(int machines, Job[] jobs) {
        String ans = "";
        int index = 0;

        for (int x = 0; x < N; x++) {
            if (index == M) {
                ans += "0\n";
            } else {
                for (int y = 0; y < machines; y++) {
                    if (index == M) {
                        ans += "0 ";
                    } else {
                        ans += jobs[index].index + " ";
                        index++;
                    }
                }
                ans += "0\n";
            }
        }
        return ans.substring(0, ans.length() - 1);
    }

    public static boolean simulate(int machines, Job[] jobs) {
        if (machines * N < M) {
            return false;
        }
        int dayNum = 1;
        int index = 0;

        int customer = 0;
        while (dayNum != N + 1) {
            if (index == M) {
                return true;
            }
            Job a = jobs[index];
            if (a.day > dayNum) { // Not that day yet
                dayNum++;
                continue;
            }
            if (dayNum - a.day > D) {
                return false;
            } // Maximum delay is the current day - job assigned

            customer++;
            index++;

            if (customer == machines) {
                dayNum++;
                customer = 0;
            }
        }
        return true;
    }
}

• Subtask 1: 0 / 100