Submission #1106484

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1106484	2024-10-30T12:52:42 Z	tungdao17	Job Scheduling (CEOI12_jobs)	Java 11	45 / 100	1000 ms	61480 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));
        }

        // 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
        // // todo: check if the remaining in processingJobs can be completed
        // while (processingJobs.size() < maxMachine && i < jobs.length &&
        // jobs[i].requestDay <= today)
        // processingJobs.add(jobs[i++]);
        // }
        // jobSchedule.add(new ArrayList<>(processingJobs));
        // today++;
        // }
        result = jobSchedule;
        return true;
    }

    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

45.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	535 ms	30916 KB	Output is correct
2	Correct	524 ms	30960 KB	Output is correct
3	Correct	516 ms	30696 KB	Output is correct
4	Correct	512 ms	30812 KB	Output is correct
5	Correct	508 ms	30752 KB	Output is correct
6	Correct	507 ms	30536 KB	Output is correct
7	Correct	520 ms	30768 KB	Output is correct
8	Correct	523 ms	30496 KB	Output is correct
9	Execution timed out	1057 ms	36404 KB	Time limit exceeded
10	Execution timed out	1058 ms	36672 KB	Time limit exceeded
11	Correct	991 ms	29840 KB	Output is correct
12	Execution timed out	1086 ms	37632 KB	Time limit exceeded
13	Execution timed out	1087 ms	32028 KB	Time limit exceeded
14	Execution timed out	1056 ms	36872 KB	Time limit exceeded
15	Execution timed out	1069 ms	43160 KB	Time limit exceeded
16	Execution timed out	1075 ms	51576 KB	Time limit exceeded
17	Execution timed out	1063 ms	51560 KB	Time limit exceeded
18	Execution timed out	1077 ms	51844 KB	Time limit exceeded
19	Execution timed out	1081 ms	61480 KB	Time limit exceeded
20	Execution timed out	1048 ms	51784 KB	Time limit exceeded