Submission #675342

#	Time	Username	Problem	Language	Result	Execution time	Memory
675342		wisePigOnTheMoon	Job Scheduling (CEOI12_jobs)	Java	40 / 100	1096 ms	55744 KiB

jobs

import java.util.*;
import java.io.*;
public class jobs {
    static class Job implements Comparable<Job> {
        public int id, day;
        public Job(int i, int d) {
            id = i;
            day = d;
        }
        public int compareTo(Job o) {
            return this.day - o.day;
        }
    }
    public static void main(String[] args) throws Exception {
        Kattio in = new Kattio();
        int days = in.nextInt();
        int d = in.nextInt();
        int m = in.nextInt();
        Job[] jobs = new Job[m];
        for (int i = 0; i < m; i++) {
            int assign = in.nextInt();
            jobs[i] = new Job(i + 1, assign);
        }
        Arrays.sort(jobs);
        int l = 0;
        int r = m;
        while (l < r) {
            int mid = (l + r)/2;
            if (checkValid(mid, days, d, m, jobs)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        System.out.println(l);
        printer(l, days, d, m, jobs);
    }
    public static boolean checkValid(int macs, int days, int d, int m, Job[] jobs) {
        int i = 0;
        int count = 1;
        while (count <= days && i < m) {
            int work = 0;
            while (work < macs && i < m) {
                if (jobs[i].day > count) {
                    break;
                }
                if (count > jobs[i].day + d) {
                    return false;
                }
                work++;
                i++;
            }
            count++;
        }
        if (i < m) {
            return false;
        }
        return true;
    }
    public static void printer(int macs, int days, int d, int m, Job[] jobs) {
        StringBuilder sb = new StringBuilder();
        int i = 0;
        int count = 1;
        while (count <= days && i < m) {
            int work = 0;
            while (work < macs && i < m) {
                if (jobs[i].day > count) {
                    break;
                }
                sb.append(jobs[i].id);
                sb.append(" ");
                work++;
                i++;
            }
            count++;
            sb.append("0\n");
        }
        while (count <= days) {
            sb.append("0\n");
            count++;
        }
        System.out.println(sb);
    }
    static class Kattio extends PrintWriter {//Kattio
        private BufferedReader r;
        private StringTokenizer st;
        // standard input
        public Kattio() { this(System.in, System.out); }
        public Kattio(InputStream i, OutputStream o) {
            super(o);
            r = new BufferedReader(new InputStreamReader(i));
        }
        // USACO-style file input
        public Kattio(String problemName) throws IOException {
            super(problemName + ".out");
            r = new BufferedReader(new FileReader(problemName + ".in"));
        }
        // returns null if no more input
        public String next() {
            try {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(r.readLine());
                return st.nextToken();
            } catch (Exception e) { }
            return null;
        }
        public int nextInt() { return Integer.parseInt(next()); }
        public double nextDouble() { return Double.parseDouble(next()); }
        public long nextLong() { return Long.parseLong(next()); }
    }
}

• Subtask 1: 40 / 100