Submission #726566

#	Time	Username	Problem	Language	Result	Execution time	Memory
726566		jnjwnwnw	Job Scheduling (CEOI12_jobs)	Java	40 / 100	1084 ms	65536 KiB

jobs

import java.util.*;
import java.io.*;
public class jobs {

    private int n, d, m;
    private int[][] arr;

    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];
        sc = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) { arr[i] = new int[]{i+1, Integer.parseInt(sc.nextToken())};}
        br.close();
        Arrays.sort(arr, (a, b) -> a[1]-b[1]);

        int lb = 1, 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] + " ");
            }
            System.out.println(0);
        }
    }

    public boolean works(int numMachines){
        int curMachines = numMachines, day = 1;
        for(int i = 0; i < m; i++){
            if (arr[i][1] > day){day = arr[i][1]; curMachines = numMachines;}
            if (arr[i][1] + d < day){
                return false;
            }
            curMachines--;
            if (curMachines == 0){curMachines = numMachines; day++;}
        }return true;
    }
}

• Subtask 1: 40 / 100