Submission #513003

#	Time	Username	Problem	Language	Result	Execution time	Memory
513003		ryankim0709	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1104 ms	56728 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;
        }
    }

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

        int N = Integer.parseInt(st.nextToken()); // # of days organization works
        int D = Integer.parseInt(st.nextToken()); // Maximum permitted delay
        int 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 = 20;

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

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

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

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

    public static int simulate(int machines, Job[] jobs, int days) {
        if (machines * days < jobs.length) {
            return Integer.MAX_VALUE;
        }
        int dayNum = 1;
        int index = 0;

        int maxDelay = 0;

        int customer = 0;
        while (dayNum != days + 1) {
            if (index == jobs.length) {
                return maxDelay;
            }
            Job a = jobs[index];
            if (a.day > dayNum) { // Not that day yet
                dayNum++;
                continue;
            }
            maxDelay = Math.max(maxDelay, dayNum - a.day); // Maximum delay is the current day - job assigned

            customer++;

            if (customer == machines) {
                dayNum++;
                customer = 0;
                index++;
                continue;
            }
            index++;
        }
        return maxDelay;
    }
}

• Subtask 1: 0 / 100