Submission #1106457

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1106457	2024-10-30T11:24:45 Z	tungdao17	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	1000 ms	64984 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<>();
        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 >= nRunningDay)
                    processingJobs.remove(0);

                // add new jobs
                while (processingJobs.size() < maxMachine && i < jobs.length && jobs[i].requestDay <= today)
                    processingJobs.add(jobs[i++]);
            }
            today++;
            jobSchedule.add(new ArrayList<>(processingJobs));
        }
        boolean isValid = today <= nDay && 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	506 ms	30228 KB	Output isn't correct
2	Incorrect	491 ms	29988 KB	Output isn't correct
3	Incorrect	514 ms	29900 KB	Output isn't correct
4	Incorrect	509 ms	28948 KB	Output isn't correct
5	Incorrect	533 ms	30272 KB	Output isn't correct
6	Incorrect	502 ms	30228 KB	Output isn't correct
7	Incorrect	497 ms	29648 KB	Output isn't correct
8	Incorrect	502 ms	30280 KB	Output isn't correct
9	Execution timed out	1050 ms	34956 KB	Time limit exceeded
10	Execution timed out	1071 ms	36432 KB	Time limit exceeded
11	Execution timed out	1067 ms	42168 KB	Time limit exceeded
12	Execution timed out	1063 ms	64984 KB	Time limit exceeded
13	Execution timed out	1035 ms	33584 KB	Time limit exceeded
14	Execution timed out	1061 ms	58476 KB	Time limit exceeded
15	Execution timed out	1070 ms	45212 KB	Time limit exceeded
16	Execution timed out	1062 ms	54368 KB	Time limit exceeded
17	Execution timed out	1061 ms	54712 KB	Time limit exceeded
18	Execution timed out	1069 ms	54804 KB	Time limit exceeded
19	Execution timed out	1065 ms	64948 KB	Time limit exceeded
20	Execution timed out	1057 ms	54852 KB	Time limit exceeded