Submission #343979

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
343979	2021-01-05T01:30:06 Z	vijay	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	501 ms	65536 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(new FileInputStream(new File("job.in"))));
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

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

        N = Integer.parseInt(first[0]);
        D = Integer.parseInt(first[1]);
        M = Integer.parseInt(first[2]);

        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	Incorrect	262 ms	21072 KB	Unexpected end of file - int32 expected
2	Incorrect	272 ms	21088 KB	Unexpected end of file - int32 expected
3	Incorrect	270 ms	21052 KB	Unexpected end of file - int32 expected
4	Incorrect	269 ms	21088 KB	Unexpected end of file - int32 expected
5	Incorrect	280 ms	20960 KB	Unexpected end of file - int32 expected
6	Incorrect	271 ms	21088 KB	Unexpected end of file - int32 expected
7	Incorrect	268 ms	21216 KB	Unexpected end of file - int32 expected
8	Incorrect	283 ms	21244 KB	Unexpected end of file - int32 expected
9	Incorrect	307 ms	21020 KB	Unexpected end of file - int32 expected
10	Incorrect	265 ms	20960 KB	Unexpected end of file - int32 expected
11	Incorrect	289 ms	21420 KB	Unexpected end of file - int32 expected
12	Incorrect	321 ms	30884 KB	Unexpected end of file - int32 expected
13	Runtime error	359 ms	40072 KB	Memory limit exceeded
14	Runtime error	418 ms	60768 KB	Memory limit exceeded
15	Runtime error	468 ms	61988 KB	Memory limit exceeded
16	Runtime error	501 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
17	Runtime error	430 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Runtime error	418 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Runtime error	414 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Runtime error	431 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)