Submission #726463

#	Time	Username	Problem	Language	Result	Execution time	Memory
726463		jnjwnwnw	Job Scheduling (CEOI12_jobs)	Java	30 / 100	1084 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;

    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]);
        // for(int[] arrr: arr){
        //     System.out.println(arrr[0] + " " + arrr[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 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);
        if(numMachines == 1){
            int a = 113;
        }
        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: 30 / 100