Submission #1106486

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1106486	2024-10-30T13:00:11 Z	tungdao17	Job Scheduling (CEOI12_jobs)	Java 11	0 / 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>> 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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	494 ms	30132 KB	Output isn't correct
2	Incorrect	492 ms	29644 KB	Output isn't correct
3	Incorrect	503 ms	29968 KB	Output isn't correct
4	Incorrect	507 ms	29660 KB	Output isn't correct
5	Incorrect	511 ms	29636 KB	Output isn't correct
6	Incorrect	522 ms	29908 KB	Output isn't correct
7	Incorrect	531 ms	29944 KB	Output isn't correct
8	Incorrect	532 ms	29836 KB	Output isn't correct
9	Execution timed out	1066 ms	34364 KB	Time limit exceeded
10	Execution timed out	1062 ms	34636 KB	Time limit exceeded
11	Execution timed out	1077 ms	43244 KB	Time limit exceeded
12	Execution timed out	1068 ms	65536 KB	Time limit exceeded
13	Execution timed out	1070 ms	32280 KB	Time limit exceeded
14	Execution timed out	1051 ms	56688 KB	Time limit exceeded
15	Execution timed out	1072 ms	43160 KB	Time limit exceeded
16	Execution timed out	1060 ms	64024 KB	Time limit exceeded
17	Execution timed out	1052 ms	51356 KB	Time limit exceeded
18	Execution timed out	1062 ms	51860 KB	Time limit exceeded
19	Execution timed out	1075 ms	61672 KB	Time limit exceeded
20	Execution timed out	1052 ms	53116 KB	Time limit exceeded