Submission #1021582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021582		QuantumPi	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1098 ms	58824 KiB

jobs

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