답안 #1119370

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1119370	2024-11-27T01:45:31 Z	hujo	Job Scheduling (CEOI12_jobs)	Java 11	55 / 100	1000 ms	65536 KB

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.end<i || top.start >i){
                    break;
                }
                else{
                    q.poll();
                    nleft--;
                }
            }
        }
        if(q.isEmpty()){
            return true;
        }
        else{return false;}
    }
    static void printRes(int min){
        pr.println(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

55.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	660 ms	28932 KB	Output is correct
2	Correct	696 ms	28796 KB	Output is correct
3	Correct	684 ms	29288 KB	Output is correct
4	Correct	691 ms	28804 KB	Output is correct
5	Correct	704 ms	28804 KB	Output is correct
6	Correct	696 ms	29052 KB	Output is correct
7	Correct	707 ms	28788 KB	Output is correct
8	Correct	696 ms	29048 KB	Output is correct
9	Correct	960 ms	28932 KB	Output is correct
10	Correct	882 ms	29064 KB	Output is correct
11	Correct	855 ms	28784 KB	Output is correct
12	Runtime error	873 ms	41672 KB	Memory limit exceeded
13	Execution timed out	1051 ms	55888 KB	Time limit exceeded
14	Execution timed out	1046 ms	65536 KB	Time limit exceeded
15	Runtime error	818 ms	65536 KB	Execution killed with signal 9
16	Runtime error	877 ms	65536 KB	Execution killed with signal 9
17	Runtime error	984 ms	65536 KB	Execution killed with signal 9
18	Runtime error	921 ms	65536 KB	Execution killed with signal 9
19	Runtime error	785 ms	65536 KB	Execution killed with signal 9
20	Runtime error	998 ms	65536 KB	Execution killed with signal 9