Submission #726451

#	Time	Username	Problem	Language	Result	Execution time	Memory
726451		jnjwnwnw	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1093 ms	51784 KiB

jobs

import java.util.*;
public class jobs {
    private class Pair{
        int ind, v;
        public Pair(int index, int val){
            this.ind = index;
            this.v = val;
        }
        public int compareTo(Pair p){
            return this.v - p.v;
        }
    }
    
    
    private int n, d, m;
    private Pair[] arr;

    public static void main(String[] args) {
        new jobs();
    }

    public jobs(){
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        d = sc.nextInt();
        m = sc.nextInt();
        arr = new Pair[m];
        for (int i = 0; i < m; i++) { arr[i] = new Pair(i, sc.nextInt()); }
        sc.close();
        Arrays.sort(arr, (a, b) -> a.compareTo(b));

        int lb = 0, ub = m, mid;
        while (lb < ub){
            mid = (lb+ub)/2;
            if (works(mid)){ub = mid;}
            else{lb = mid+1;}
        }

        System.out.println(lb);
        int j = 0;
        for(int i = 0; i < n; i++){
            int end = Math.min(m, j + lb);
            for(; j < end; j++){
                if (arr[j].v > i+1){break;}
                System.out.print(arr[j].ind + 1 + " ");
            }
            System.out.println(0);
        }
    }

    public boolean works(int numMachines){
        int done = 0;
        for(int days = 1; days<=(n-d); days++){
            int end = Math.min(m, done+numMachines);
            for (;done<end;done++){
                if (arr[done].v > days){
                    break;
                }
            }
        } return (done==m);
    }
}

• Subtask 1: 0 / 100