Submission #343978

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
343978	2021-01-05T01:28:16 Z	vijay	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	75 ms	8732 KB

jobs

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

public class jobs {

    static int N, D, M;
    static Pair[] requests;
    public static void main(String[] args) throws IOException, FileNotFoundException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(reader.readLine());
        D = Integer.parseInt(reader.readLine());
        M = Integer.parseInt(reader.readLine());

        requests = new Pair[M];

        String[] valString = reader.readLine().split(" ");

        for(int i = 0; i < M; i++){
            requests[i] = new Pair(Integer.parseInt(valString[i]), i + 1);
        }

        if(M >= 0){
            return;
        }

        Arrays.sort(requests);

        int a = 1;
        int b = 1000000;
        while(a != b){
            int mid = (a + b)/2;
            if(works(mid)){
                b = mid;
            } else {
                a = mid + 1;
            }
        }

        String[] returns = new String[N];
        int machineIdx = 0;
        int[] lastTask = new int[a];
        for(int i = 0; i < M; i++){
            lastTask[machineIdx] = Math.max(lastTask[machineIdx] + 1, requests[i].a);
            int idx = lastTask[machineIdx] - 1;
            if(returns[idx] == null){
                returns[idx] = String.valueOf(requests[i].b);
            } else {
                returns[idx] += " " + requests[i].b;
            }
            machineIdx++;
            machineIdx %= a;
        }

        System.out.println(a);
        for(int i = 0; i < N; i++){
            if(returns[i] != null){
                System.out.println(returns[i] + " 0");
            } else {
                System.out.println("0");
            }
        }
    }

    public static boolean works(int machines){
        int[] lastTask = new int[machines];
        int machineIdx = 0;
        for(int i = 0; i < M; i++){
            lastTask[machineIdx] = Math.max(lastTask[machineIdx] + 1, requests[i].a);
            if(lastTask[machineIdx] - requests[i].a > D){
                return false;
            }
            machineIdx++;
            machineIdx %= machines;
        }

        return true;
    }

    static class Pair implements Comparable<Pair>{
        int a, b;
        public Pair(int a, int b){
            this.a = a;
            this.b = b;
        }

        public int compareTo(Pair p){
            return a - p.a;
        }
    }
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	70 ms	8556 KB	Execution failed because the return code was nonzero
2	Runtime error	72 ms	8488 KB	Execution failed because the return code was nonzero
3	Runtime error	71 ms	8528 KB	Execution failed because the return code was nonzero
4	Runtime error	71 ms	8556 KB	Execution failed because the return code was nonzero
5	Runtime error	71 ms	8556 KB	Execution failed because the return code was nonzero
6	Runtime error	74 ms	8540 KB	Execution failed because the return code was nonzero
7	Runtime error	71 ms	8556 KB	Execution failed because the return code was nonzero
8	Runtime error	74 ms	8556 KB	Execution failed because the return code was nonzero
9	Runtime error	71 ms	8656 KB	Execution failed because the return code was nonzero
10	Runtime error	72 ms	8556 KB	Execution failed because the return code was nonzero
11	Runtime error	74 ms	8668 KB	Execution failed because the return code was nonzero
12	Runtime error	70 ms	8732 KB	Execution failed because the return code was nonzero
13	Runtime error	72 ms	8428 KB	Execution failed because the return code was nonzero
14	Runtime error	74 ms	8428 KB	Execution failed because the return code was nonzero
15	Runtime error	71 ms	8428 KB	Execution failed because the return code was nonzero
16	Runtime error	72 ms	8428 KB	Execution failed because the return code was nonzero
17	Runtime error	74 ms	8556 KB	Execution failed because the return code was nonzero
18	Runtime error	75 ms	8428 KB	Execution failed because the return code was nonzero
19	Runtime error	71 ms	8576 KB	Execution failed because the return code was nonzero
20	Runtime error	71 ms	8556 KB	Execution failed because the return code was nonzero