Submission #1106489

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1106489	2024-10-30T13:08:22 Z	tungdao17	Job Scheduling (CEOI12_jobs)	Java 11	40 / 100	1000 ms	65536 KB

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>> dailySchedule = new ArrayList<>();
        List<Job> processingJobs = new LinkedList<>();
        int today = 1, i = 0;
        while (today <= nDay && i < jobs.length) {
            // 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) {
                // ! only add jobs whose deadline >= today
                // if see a deadline job -> return immediately
                int deadline = jobs[i].requestDay + nRunningDay;
                if (deadline < today)
                    return false;
                processingJobs.add(jobs[i++]);
            }
            dailySchedule.add(new ArrayList<>(processingJobs));
            today++;
        }
        boolean isValid = i == jobs.length;
        if (isValid)
            result = dailySchedule;
        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

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	505 ms	30424 KB	Output is correct
2	Correct	515 ms	30368 KB	Output is correct
3	Correct	506 ms	30948 KB	Output is correct
4	Correct	506 ms	30384 KB	Output is correct
5	Correct	520 ms	30372 KB	Output is correct
6	Correct	513 ms	30456 KB	Output is correct
7	Correct	516 ms	30748 KB	Output is correct
8	Correct	518 ms	30360 KB	Output is correct
9	Execution timed out	1065 ms	28204 KB	Time limit exceeded
10	Execution timed out	1057 ms	27748 KB	Time limit exceeded
11	Execution timed out	1066 ms	42952 KB	Time limit exceeded
12	Execution timed out	1037 ms	65536 KB	Time limit exceeded
13	Execution timed out	1057 ms	32620 KB	Time limit exceeded
14	Execution timed out	1064 ms	56768 KB	Time limit exceeded
15	Execution timed out	1062 ms	43292 KB	Time limit exceeded
16	Execution timed out	1038 ms	51036 KB	Time limit exceeded
17	Execution timed out	1063 ms	53412 KB	Time limit exceeded
18	Execution timed out	1058 ms	51908 KB	Time limit exceeded
19	Execution timed out	1070 ms	61668 KB	Time limit exceeded
20	Execution timed out	1070 ms	51476 KB	Time limit exceeded