Submission #361442

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
361442	2021-01-30T08:10:20 Z	AnythingWithJ	Job Scheduling (CEOI12_jobs)	Java 11	40 / 100	1000 ms	65536 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	799 ms	24036 KB	Output is correct
2	Correct	749 ms	24112 KB	Output is correct
3	Correct	791 ms	24020 KB	Output is correct
4	Correct	791 ms	24056 KB	Output is correct
5	Correct	784 ms	23892 KB	Output is correct
6	Correct	750 ms	24052 KB	Output is correct
7	Correct	772 ms	23868 KB	Output is correct
8	Correct	785 ms	24020 KB	Output is correct
9	Execution timed out	1086 ms	20928 KB	Time limit exceeded
10	Execution timed out	1088 ms	21648 KB	Time limit exceeded
11	Execution timed out	1086 ms	22600 KB	Time limit exceeded
12	Execution timed out	1083 ms	30148 KB	Time limit exceeded
13	Execution timed out	1095 ms	41672 KB	Time limit exceeded
14	Execution timed out	1083 ms	49260 KB	Time limit exceeded
15	Execution timed out	1083 ms	60800 KB	Time limit exceeded
16	Runtime error	627 ms	65536 KB	Execution killed with signal 9
17	Runtime error	594 ms	65536 KB	Execution killed with signal 9
18	Runtime error	617 ms	65536 KB	Execution killed with signal 9
19	Runtime error	598 ms	65536 KB	Execution killed with signal 9
20	Runtime error	633 ms	65536 KB	Execution killed with signal 9