Submission #726456

#	Time	Username	Problem	Language	Result	Execution time	Memory
726456		jnjwnwnw	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1087 ms	65536 KiB

jobs

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

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

    public jobs() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer sc = new StringTokenizer(br.readLine());
        n = Integer.parseInt(sc.nextToken());
        d = Integer.parseInt(sc.nextToken());
        m = Integer.parseInt(sc.nextToken());
        arr = new int[m][2];
        toDoPerDay = new int[n+1];
        int k;
        sc = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) { arr[i] = new int[]{i, k = Integer.parseInt(sc.nextToken())}; toDoPerDay[k]++;}
        br.close();
        Arrays.sort(arr, (a, b) -> a[1]-b[1]);

        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][1] > i+1){break;}
                System.out.print(arr[j][0] + 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][1] > days){
        //             break;
        //         }
        //     }
        // } return (done==m);
        int toDo = 0;
        for(int i = 1; i <= (n-d); i++){
            toDo += toDoPerDay[i];
            toDo = Math.max(0, toDo-numMachines);
        }
        return (toDo == 0);
    }
}

• Subtask 1: 0 / 100