Submission #343977

#	Time	Username	Problem	Language	Result	Execution time	Memory
343977		vijay	Job Scheduling (CEOI12_jobs)	Java	0 / 100	77 ms	8812 KiB

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