Submission #1160792

#TimeUsernameProblemLanguageResultExecution timeMemory
1160792abdulaziz707Job Scheduling (CEOI12_jobs)Java
40 / 100
1100 ms98812 KiB
import java.io.*;
import java.util.*;

public class jobs {
    public static class Request {
        public int requestNumber;
        public int recievedDay;
        public int processedDay;

        public Request(int requestNumber, int recievedDay) {
            this.requestNumber = requestNumber;
            this.recievedDay = recievedDay;
        }
    }

    public static class daySchedule {
        public int dayNumber;
        public int requestCount;

        public daySchedule(int dayNumber, int requestCount) {
            this.dayNumber = dayNumber;
            this.requestCount = requestCount;
        }
    }

    public static void main(String[] args) {
        Kattio io = new Kattio();

        int n, d, m;

        n = io.nextInt();
        d = io.nextInt();
        m = io.nextInt();

        Request[] requests = new Request[m];

        for (int x, i = 0; i < m; i++) {
            x = io.nextInt();
            requests[i] = new Request(i + 1, x + 0);
        }

        Arrays.sort(requests, (r, l) -> r.recievedDay - l.recievedDay);

        PriorityQueue<daySchedule> pq = new PriorityQueue<>((r, l) -> {
            if (r.requestCount != l.requestCount)
                return r.requestCount - l.requestCount;
            return r.dayNumber - l.dayNumber;
        });

        for (int i = 1; i <= d; i++)
            pq.add(new daySchedule(i, 0));

        int pos = 0;
        for(int day = 1; day <= n && pos < m; day++) {
            pq.add(new daySchedule(day + d, 0));

            if (day < requests[pos].recievedDay)
                continue;

            while(pos < m && requests[pos].recievedDay == day) {
                daySchedule schedule = pq.poll();
                
                if (schedule.dayNumber < day)
                    continue;
                
                schedule.requestCount++;
                requests[pos++].processedDay = schedule.dayNumber;
                pq.add(schedule);
            }
        }

        Arrays.sort(requests, (r, l) -> r.processedDay - l.processedDay);

        int minimumMachines = Integer.MIN_VALUE;
        for(int ipos, i = 0; i < m; ) {
            ipos = i;
            while(i < m && requests[i].processedDay == requests[ipos].processedDay)
                i++;

            if (i - ipos > minimumMachines)
                minimumMachines = i - ipos;
        }

        io.println(minimumMachines);

        pos = 0;
        for(int day = 1; day <= n; day++) {
            while(pos < m && requests[pos].processedDay == day) {
                io.print(requests[pos++].requestNumber + " ");
            }

            io.println(0);
        }

        io.close();
    }

    static class Kattio extends PrintWriter {
        private BufferedReader r;
        private StringTokenizer st;
        // standard input
        public Kattio() { this(System.in, System.out); }
        public Kattio(InputStream i, OutputStream o) {
            super(o);
            r = new BufferedReader(new InputStreamReader(i));
        }
        // USACO-style file input
        public Kattio(String problemName) throws IOException {
            super(problemName + ".out");
            r = new BufferedReader(new FileReader(problemName + ".in"));
        }
        // returns null if no more input
        public String next() {
            try {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(r.readLine());
                return st.nextToken();
            } catch (Exception e) { }
            return null;
        }
        public int nextInt() { return Integer.parseInt(next()); }
        public double nextDouble() { return Double.parseDouble(next()); }
        public long nextLong() { return Long.parseLong(next()); }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...