Submission #1106488

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1106488	2024-10-30T13:04:56 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>> 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) {
            // 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 >= today)
                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

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	601 ms	29704 KB	Output is correct
2	Correct	606 ms	30108 KB	Output is correct
3	Correct	593 ms	30280 KB	Output is correct
4	Correct	603 ms	29988 KB	Output is correct
5	Correct	601 ms	29840 KB	Output is correct
6	Correct	603 ms	29872 KB	Output is correct
7	Correct	604 ms	29992 KB	Output is correct
8	Correct	631 ms	30128 KB	Output is correct
9	Execution timed out	1063 ms	36556 KB	Time limit exceeded
10	Execution timed out	1069 ms	34480 KB	Time limit exceeded
11	Execution timed out	1064 ms	43316 KB	Time limit exceeded
12	Execution timed out	1032 ms	65536 KB	Time limit exceeded
13	Execution timed out	1074 ms	32372 KB	Time limit exceeded
14	Execution timed out	1084 ms	65536 KB	Time limit exceeded
15	Execution timed out	1029 ms	43452 KB	Time limit exceeded
16	Execution timed out	1068 ms	64228 KB	Time limit exceeded
17	Execution timed out	1066 ms	53284 KB	Time limit exceeded
18	Execution timed out	1076 ms	51856 KB	Time limit exceeded
19	Execution timed out	1056 ms	61684 KB	Time limit exceeded
20	Execution timed out	1072 ms	53388 KB	Time limit exceeded