Submission #1119363

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119363	2024-11-27T01:32:27 Z	hujo	Job Scheduling (CEOI12_jobs)	Java 11	0 / 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.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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	581 ms	29444 KB	Output isn't correct
2	Incorrect	624 ms	29024 KB	Output isn't correct
3	Incorrect	612 ms	29224 KB	Output isn't correct
4	Incorrect	605 ms	28804 KB	Output isn't correct
5	Incorrect	601 ms	28916 KB	Output isn't correct
6	Incorrect	579 ms	28748 KB	Output isn't correct
7	Incorrect	560 ms	28768 KB	Output isn't correct
8	Incorrect	608 ms	28948 KB	Output isn't correct
9	Incorrect	903 ms	28912 KB	Expected EOLN
10	Incorrect	720 ms	28872 KB	Expected EOLN
11	Incorrect	755 ms	28916 KB	Expected EOLN
12	Runtime error	849 ms	42044 KB	Memory limit exceeded
13	Execution timed out	1046 ms	56136 KB	Time limit exceeded
14	Execution timed out	1061 ms	65536 KB	Time limit exceeded
15	Runtime error	779 ms	65536 KB	Execution killed with signal 9
16	Runtime error	809 ms	65536 KB	Execution killed with signal 9
17	Runtime error	955 ms	65536 KB	Execution killed with signal 9
18	Runtime error	946 ms	65536 KB	Execution killed with signal 9
19	Runtime error	761 ms	65536 KB	Execution killed with signal 9
20	Runtime error	935 ms	65536 KB	Execution killed with signal 9