oj.uz

Submission #1021582

# Submission time Handle Problem Language Result Execution time Memory
1021582 2024-07-12T20:22:23 Z QuantumPi Job Scheduling (CEOI12_jobs) Java 11
0 / 100
 1000 ms 58824 KB 
import java.io.*;
import java.util.*;
 
public class jobs {
    static class Point implements Comparable<Point> {
        int time;
        int position;
        public Point(int time, int position){
            this.time = time;
            this.position = position;
        }
        @Override
        public int compareTo(Point c) {
            return Integer.compare(time, c.time);
        }
        @Override
        public String toString() {
            return time+" "+position;
        }
    }
    public static int n, d, m;
    public static ArrayList<ArrayList<Integer>> jobs = new ArrayList<>();
    public static String s = "";
    public static void main(String[] args) {
        Scanner fin = new Scanner(System.in);
        
        n = fin.nextInt();
        d = fin.nextInt();
        m = fin.nextInt();
        for (int i=0; i<n-d; i++) {
            jobs.add(new ArrayList<>());
        }
        for (int i=0; i<m; i++) {
            jobs.get(fin.nextInt()-1).add(i);
        }
        int low = 1;
        int high = m;
        while (low < high) {
            int mid = (low+high)/2;
            if (works(mid)) {
                high = mid;
            }
            else {
                low = mid+1;
            }
        }
        System.out.println(low);
        System.out.println(s);

        fin.close();
    }
    public static boolean works(int numMachines) {
        PriorityQueue<Point> pq = new PriorityQueue<>();
        String tempS = "";
        for (int i=0; i<n; i++) {
            if (i < n-d) {
                for (int j=0; j<jobs.get(i).size(); j++) {
                    pq.add(new Point(i, jobs.get(i).get(j)));
                }
            }
            if (!tempS.equals("")) {
                tempS += "\n";
            }
            for (int j=0; j<numMachines; j++) {
                if (pq.isEmpty()) {
                    break;
                }
                Point p = pq.poll();
                if (p.time+d < i) {
                    return false;
                }
                tempS += (p.position+1)+" ";
            }
            tempS += "0";
        }
        if (!pq.isEmpty()) {
            return false;
        }
        s = tempS; 
        return true;
    }
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1026 ms 28056 KB Time limit exceeded
2 Execution timed out 1044 ms 27264 KB Time limit exceeded
3 Execution timed out 1022 ms 27424 KB Time limit exceeded
4 Execution timed out 1053 ms 27320 KB Time limit exceeded
5 Execution timed out 1055 ms 27452 KB Time limit exceeded
6 Execution timed out 1055 ms 27700 KB Time limit exceeded
7 Execution timed out 1016 ms 27456 KB Time limit exceeded
8 Execution timed out 1028 ms 27688 KB Time limit exceeded
9 Execution timed out 1037 ms 27676 KB Time limit exceeded
10 Execution timed out 1075 ms 28068 KB Time limit exceeded
11 Execution timed out 1061 ms 23824 KB Time limit exceeded
12 Execution timed out 1044 ms 26092 KB Time limit exceeded
13 Execution timed out 1064 ms 30480 KB Time limit exceeded
14 Execution timed out 1078 ms 35176 KB Time limit exceeded
15 Execution timed out 1039 ms 37236 KB Time limit exceeded
16 Execution timed out 1054 ms 43672 KB Time limit exceeded
17 Execution timed out 1028 ms 43952 KB Time limit exceeded
18 Execution timed out 1075 ms 48984 KB Time limit exceeded
19 Execution timed out 1098 ms 58824 KB Time limit exceeded
20 Execution timed out 1061 ms 43980 KB Time limit exceeded