Submission #401920

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
401920	2021-05-11T01:48:38 Z	rainliofficial	Job Scheduling (CEOI12_jobs)	Java 11	40 / 100	1000 ms	65540 KB

jobs

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
 
public class jobs {
    // 7 mins planning
    static int N,D,M;
    static Integer [][] requests;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer s = new StringTokenizer(br.readLine());
        N = Integer.parseInt(s.nextToken());
        D = Integer.parseInt(s.nextToken());
        M = Integer.parseInt(s.nextToken());
        requests = new Integer [M][2]; // day, orgInd
        s = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            requests[i][0] = Integer.parseInt(s.nextToken());
            requests[i][1] = i+1;
        }
        Arrays.sort(requests, (integers, t1) -> integers[0] - t1[0]);
        int a = 1, b = M;
        while (a != b) {
            int mid = (a+b)/2;
            if (works(mid)) b=mid;
            else a = mid+1;
        }
        out.println(b);
        int [] lastDays = new int [b];
        ArrayList<Integer>[]days = new ArrayList[N+1];
        for (int i = 1; i <= N; i++) days[i] = new ArrayList<>();
        for (int i = 0, currMach = 0; i < M; i++,currMach++) {
            int currDay = requests[i][0];
            if (currMach == b) currMach = 0;
            int nextMachDay = lastDays[currMach]+1;
            lastDays[currMach] = Math.max(nextMachDay, currDay);
            days[Math.max(nextMachDay,currDay)].add(requests[i][1]);
        }
        for (int i = 1; i <= N; i++) {
            if (days[i] != null) {
                for (int num : days[i]) out.print(num+" ");
            }
            out.println(0);
        }
        out.close();
    }
    static boolean works (int numMachines) {
        int [] lastDays = new int [numMachines];
        int maxD = 0;
        for (int i = 0, currMach = 0; i < M; i++,currMach++) {
            int currDay = requests[i][0];
            if (currMach == numMachines) currMach = 0;
            int nextMachDay = lastDays[currMach]+1;
            if (nextMachDay > currDay) {
                maxD = Math.max(maxD,nextMachDay-currDay);
                lastDays[currMach] = nextMachDay;
            }
            else {
                lastDays[currMach] = currDay;
            }
        }
        return maxD <= D;
    }
}

Compilation message

Note: jobs.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	727 ms	23648 KB	Output is correct
2	Correct	729 ms	23604 KB	Output is correct
3	Correct	739 ms	23604 KB	Output is correct
4	Correct	734 ms	23700 KB	Output is correct
5	Correct	728 ms	23608 KB	Output is correct
6	Correct	735 ms	23628 KB	Output is correct
7	Correct	731 ms	23600 KB	Output is correct
8	Correct	734 ms	23468 KB	Output is correct
9	Execution timed out	1098 ms	20608 KB	Time limit exceeded
10	Execution timed out	1097 ms	21252 KB	Time limit exceeded
11	Execution timed out	1102 ms	22464 KB	Time limit exceeded
12	Execution timed out	1090 ms	29948 KB	Time limit exceeded
13	Execution timed out	1102 ms	42140 KB	Time limit exceeded
14	Execution timed out	1104 ms	49432 KB	Time limit exceeded
15	Execution timed out	1064 ms	60168 KB	Time limit exceeded
16	Runtime error	584 ms	65540 KB	Execution killed with signal 9
17	Runtime error	586 ms	65540 KB	Execution killed with signal 9
18	Runtime error	569 ms	65540 KB	Execution killed with signal 9
19	Runtime error	592 ms	65540 KB	Execution killed with signal 9
20	Runtime error	583 ms	65540 KB	Execution killed with signal 9