Submission #343977

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
343977	2021-01-05T01:26:03 Z	vijay	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	77 ms	8812 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);
        }

        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	71 ms	8684 KB	Execution failed because the return code was nonzero
2	Runtime error	75 ms	8668 KB	Execution failed because the return code was nonzero
3	Runtime error	72 ms	8556 KB	Execution failed because the return code was nonzero
4	Runtime error	73 ms	8552 KB	Execution failed because the return code was nonzero
5	Runtime error	73 ms	8552 KB	Execution failed because the return code was nonzero
6	Runtime error	72 ms	8556 KB	Execution failed because the return code was nonzero
7	Runtime error	74 ms	8556 KB	Execution failed because the return code was nonzero
8	Runtime error	74 ms	8528 KB	Execution failed because the return code was nonzero
9	Runtime error	73 ms	8448 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	73 ms	8556 KB	Execution failed because the return code was nonzero
12	Runtime error	77 ms	8552 KB	Execution failed because the return code was nonzero
13	Runtime error	74 ms	8556 KB	Execution failed because the return code was nonzero
14	Runtime error	73 ms	8684 KB	Execution failed because the return code was nonzero
15	Runtime error	74 ms	8428 KB	Execution failed because the return code was nonzero
16	Runtime error	73 ms	8556 KB	Execution failed because the return code was nonzero
17	Runtime error	73 ms	8556 KB	Execution failed because the return code was nonzero
18	Runtime error	73 ms	8812 KB	Execution failed because the return code was nonzero
19	Runtime error	73 ms	8812 KB	Execution failed because the return code was nonzero
20	Runtime error	73 ms	8428 KB	Execution failed because the return code was nonzero