Submission #1119477

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119477	2024-11-27T05:09:56 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	55 / 100	1000 ms	57708 KB

jobs

import java.io.*;
import java.util.*;

public class jobs {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int mxn = 1000005;
        Pair[] a = new Pair[m + 2];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= m; i++) {
            a[i] = new Pair(Integer.parseInt(st.nextToken()), i);
        }
        a[m + 1] = new Pair(1000000000, 0); // Dummy pair

        Arrays.sort(a, 1, m + 1);

        int l = 0, r = m;

        while (r - l > 1) {
            int mid = (l + r) / 2;
            int p = 1;

            for (int i = 1; i <= n; i++) {
                if (a[p].fr + d < i) {
                    break;
                }
                int cnt = 0;
                while (cnt < mid && p <= m && a[p].fr <= i) {
                    cnt++;
                    p++;
                }
            }

            if (p > m) {
                r = mid;
            } else {
                l = mid;
            }
        }

        System.out.println(r);
        int p = 1;

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            int cnt = 0;
            while (cnt < r && p <= m && a[p].fr <= i) {
                sb.append(a[p].sc).append(" ");
                cnt++;
                p++;
            }
            sb.append("0\n");
        }

        System.out.print(sb);
    }

    static class Pair implements Comparable<Pair> {
        int fr, sc;

        Pair(int fr, int sc) {
            this.fr = fr;
            this.sc = sc;
        }

        public int compareTo(Pair other) {
            return Integer.compare(this.fr, other.fr);
        }
    }
}

Subtask #1

55.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	333 ms	19312 KB	Output is correct
2	Correct	314 ms	19400 KB	Output is correct
3	Correct	306 ms	19008 KB	Output is correct
4	Correct	313 ms	18944 KB	Output is correct
5	Correct	311 ms	21076 KB	Output is correct
6	Correct	289 ms	20436 KB	Output is correct
7	Correct	288 ms	19136 KB	Output is correct
8	Correct	303 ms	18880 KB	Output is correct
9	Correct	821 ms	20600 KB	Output is correct
10	Correct	876 ms	20656 KB	Output is correct
11	Correct	839 ms	21448 KB	Output is correct
12	Execution timed out	1008 ms	26252 KB	Time limit exceeded
13	Execution timed out	1048 ms	26000 KB	Time limit exceeded
14	Execution timed out	1028 ms	33744 KB	Time limit exceeded
15	Execution timed out	1064 ms	36848 KB	Time limit exceeded
16	Execution timed out	1049 ms	43344 KB	Time limit exceeded
17	Execution timed out	1032 ms	47788 KB	Time limit exceeded
18	Execution timed out	1049 ms	48940 KB	Time limit exceeded
19	Execution timed out	1050 ms	57708 KB	Time limit exceeded
20	Execution timed out	1033 ms	47140 KB	Time limit exceeded