Submission #1119363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119363		hujo	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1061 ms	65536 KiB

jobs

import java.io.*;
import java.util.*;

public class jobs{
    static int N; static int M;
    static List<Job> jobs;
    static PrintWriter pr;
    public static void main(String []args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        pr = new PrintWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); int D = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken());
        jobs = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=M; i++){
            int id = Integer.parseInt(st.nextToken());
            jobs.add(new Job(i, id, id+D));
        }
        jobs.sort((j1, j2)->Integer.compare(j1.end, j2.end));
        int minmachine=binsearchLeft(0, M);
        printRes(minmachine);
        pr.close();
    }
    static boolean isGood(int machines){
        Queue<Job> q= new LinkedList<Job>();
        for(Job j: jobs){
            q.offer(j);
        }
        for(int i=1; i<=N; i++){
            int nleft = machines;
            while(nleft>0 && q.peek()!=null){
                Job top = q.peek();
                if(top.start >i){
                    break;
                }
                else{
                    q.poll();
                    nleft--;
                }
            }
        }
        if(q.isEmpty()){
            return true;
        }
        else{return false;}
    }
    static void printRes(int min){
        Queue<Job> q= new LinkedList<Job>();
        for(Job j: jobs){
            q.offer(j);
        }
        for(int i=1; i<=N; i++){
            int nleft = min;
            while(nleft>0 && q.peek()!=null){
                Job top = q.peek();
                if(top.start >i){
                    break;
                }
                else{
                    pr.print(top.id+" ");
                    q.poll();
                    nleft--;
                }
            }
            pr.print(0);
            pr.println();
        }
    }



    static int binsearchLeft(int left, int right){
        if(left>right){
            return -1;
        }
        int mid = left + (right-left)/2;
        if(isGood(mid)){
            int res = binsearchLeft(left, mid-1);
            if(res==-1){return mid;}
            else{return res;}
        }
        else{
            return binsearchLeft(mid+1, right);
        }
    }


    static class Job{
        int id; int start; int end;
        public Job(int id, int start, int end){
            this.id = id; this.start = start; this.end=end;
        }
    }
}

• Subtask 1: 0 / 100