oj.uz

Submission #361436

# Submission time Handle Problem Language Result Execution time Memory
361436 2021-01-30T07:51:27 Z AnythingWithJ Job Scheduling (CEOI12_jobs) Java 11
0 / 100
 1000 ms 60696 KB 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class jobs {
    // 7 mins planning
    static int N,D,M;
    static int [] requests;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer s = new StringTokenizer(br.readLine());
        N = Integer.parseInt(s.nextToken());
        D = Integer.parseInt(s.nextToken());
        M = Integer.parseInt(s.nextToken());
        requests = new int [M];
        s = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            requests[i] = Integer.parseInt(s.nextToken());
        }
        Arrays.sort(requests);
        int a = 1, b = M;
        while (a != b) {
            int mid = (a+b)/2;
            if (works(mid)) b=mid;
            else a = mid+1;
        }
        out.println(b);
        out.close();
    }
    static boolean works (int numMachines) {
        PriorityQueue<Integer> machines = new PriorityQueue<>();
        for (int i = 0; i < numMachines; i++) machines.add(0);
        int maxD = 0;
        for (int i = 0; i < M; i++) {
            int currDay = requests[i];
            int nextAvalMachineDay = machines.poll()+1;
            if (nextAvalMachineDay > currDay) {
                maxD = Math.max(maxD,nextAvalMachineDay-currDay);
            }
            machines.add(Math.max(nextAvalMachineDay,currDay));
        }
        return maxD <= D;
    }
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 603 ms 16092 KB Unexpected end of file - int32 expected
2 Incorrect 601 ms 16104 KB Unexpected end of file - int32 expected
3 Incorrect 605 ms 15928 KB Unexpected end of file - int32 expected
4 Incorrect 597 ms 16088 KB Unexpected end of file - int32 expected
5 Incorrect 595 ms 15952 KB Unexpected end of file - int32 expected
6 Incorrect 595 ms 15816 KB Unexpected end of file - int32 expected
7 Incorrect 611 ms 15840 KB Unexpected end of file - int32 expected
8 Incorrect 607 ms 16148 KB Unexpected end of file - int32 expected
9 Incorrect 753 ms 22128 KB Unexpected end of file - int32 expected
10 Incorrect 850 ms 24424 KB Unexpected end of file - int32 expected
11 Incorrect 875 ms 27772 KB Unexpected end of file - int32 expected
12 Execution timed out 1066 ms 29816 KB Time limit exceeded
13 Execution timed out 1091 ms 36780 KB Time limit exceeded
14 Execution timed out 1085 ms 42932 KB Time limit exceeded
15 Execution timed out 1082 ms 40816 KB Time limit exceeded
16 Execution timed out 1086 ms 53092 KB Time limit exceeded
17 Execution timed out 1093 ms 58568 KB Time limit exceeded
18 Execution timed out 1089 ms 60696 KB Time limit exceeded
19 Execution timed out 1088 ms 58688 KB Time limit exceeded
20 Execution timed out 1098 ms 58664 KB Time limit exceeded