Submission #1106486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106486		tungdao17	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1077 ms	65536 KiB

jobs

import java.io.*;
import java.util.*;
import java.util.function.Predicate;

// https://oj.uz/problem/view/CEOI12_jobs
public class jobs {
    static List<List<Job>> result;

    public static void main(String[] args) throws IOException {
        Kattio io = new Kattio();
        // Kattio io = new Kattio("test");

        int N = io.nextInt(), D = io.nextInt(), M = io.nextInt();
        Job[] jobs = new Job[M];
        for (int i = 0; i < M; ++i)
            jobs[i] = new Job(i + 1, io.nextInt());

        Arrays.sort(jobs, Comparator.comparingInt(j -> j.requestDay));

        io.println(firstTrue(1, M, x -> can(x, N, D, jobs)));

        for (int i = 0; i < N; ++i) {
            if (i < result.size()) {
                StringBuilder s = new StringBuilder();
                for (Job job : result.get(i))
                    s.append(job.id + " ");
                s.append("0");
                io.println(s.toString());
            } else
                io.println("0");
        }

        io.close();
    }

    static boolean can(int maxMachine, int nDay, int nRunningDay, Job[] jobs) {
        List<List<Job>> jobSchedule = new ArrayList<>();
        // int jobIdx = 0;
        // for (int today = 1; today <= nDay; ++today) {
        // List<Job> processingJobs = new LinkedList<>();
        // for (int i = 0; i < maxMachine; ++i) {
        // // skip future jobs
        // if (jobIdx == jobs.length || jobs[jobIdx].requestDay > today)
        // break;

        // // if there's a job before today,
        // // and must finish before today -> not feasible
        // if (jobs[jobIdx].requestDay + nRunningDay < today)
        // return false;

        // processingJobs.add(jobs[jobIdx++]);
        // }
        // jobSchedule.add(new ArrayList<>(processingJobs));
        // }

        List<Job> processingJobs = new LinkedList<>();
        int today = 1, i = 0;
        while (today <= nDay && i < jobs.length) {
            if (processingJobs.size() > maxMachine)
                return false;
            else {
                // remove finished jobs
                while (processingJobs.size() > 0 && today - processingJobs.get(0).requestDay
                        + 1 >= nRunningDay)
                    processingJobs.remove(0);

                // add new jobs
                while (processingJobs.size() < maxMachine && i < jobs.length &&
                        jobs[i].requestDay <= today && jobs[i].requestDay + nRunningDay <= nDay)
                    processingJobs.add(jobs[i++]);
            }
            jobSchedule.add(new ArrayList<>(processingJobs));
            today++;
        }
        boolean isValid = i == jobs.length;
        if (isValid)
            result = jobSchedule;
        return isValid;
    }

    static int firstTrue(int l, int r, Predicate<Integer> f) {
        r++;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (f.test(m))
                r = m;
            else
                l = m + 1;
        }
        return l;
    }

    static class Job {
        int id, requestDay;

        Job(int id, int day) {
            this.id = id;
            this.requestDay = day;
        }
    }
}

// 8 2 12
// 1 2 4 2 1 3 5 6 2 3 6 4

class Kattio extends PrintWriter {
    BufferedReader r;
    StringTokenizer st;

    public Kattio() {
        super(System.out);
        r = new BufferedReader(new InputStreamReader(System.in));
    }

    public Kattio(String problemName) throws IOException {
        super(problemName + ".out");
        r = new BufferedReader(new FileReader(problemName + ".in"));
    }

    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: 0 / 100