Submission #291170

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
291170	2020-09-04T19:59:35 Z	Agnimandur	Job Scheduling (CEOI12_jobs)	Java 11	0 / 100	98 ms	10488 KB

jobs

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        PrintWriter pw = new PrintWriter(System.out);
        
        int N = sc.ni();
        int D = sc.ni();
        int M = sc.ni();
        
        int[][] nums = new int[M][2];
        for (int i = 0; i < M; i++)
        	nums[i] = new int[] {sc.ni()-1,i+1};
        nums = sort(nums);
        
        int low = 1;
        int high = M;
        while (low < high) {
        	int X = (low+high)/2;
        	boolean good = true;
        	int day = -1;
        	int cur = 0;
        	for (int i = 0; i < M; i++) {
        		if (nums[i][0] > day) {
        			day = nums[i][0];
        			cur = 1;
        		} else if (cur == X) {
        			day++;
        			cur = 1;
        		} else {
        			cur++;
        		}
        		if (day-nums[i][0] > D) {
        			good = false;
        			break;
        		}
        	}
        	if (good) {
        		high = X;
        	} else {
        		low = X+1;
        	}
        }
        int X = low;
        
        ArrayList<Integer>[] ans = new ArrayList[N];
        for (int i = 0; i < N; i++)
        	ans[i] = new ArrayList<Integer>();
    	int day = -1;
    	int cur = 0;
    	for (int i = 0; i < M; i++) {
    		if (nums[i][0] > day) {
    			day = nums[i][0];
    			cur = 1;
    		} else if (cur == X) {
    			day++;
    			cur = 1;
    		} else {
    			cur++;
    		}
    		ans[day].add(nums[i][1]);
    	}
    	
    	pw.println(X);
    	for (int i = 0; i < N; i++) {
    		for (int j: ans[i])
    			pw.print(j + " ");
    		pw.println(0);
    	}

        pw.close();
    }
    
    public static int[][] sort(int[][] arr) {
    	//Sort an array (immune to quicksort TLE)
    	Random rgen = new Random();
    	for (int i = 0; i < arr.length; i++) {
    		int randomPosition = rgen.nextInt(arr.length);
    		int[] temp = arr[i];
    		arr[i] = arr[randomPosition];
    		arr[randomPosition] = temp;
    	}
    	Arrays.sort(arr, new Comparator<int[]>() {
    		@Override
    		public int compare(int[] arr1, int[] arr2) {
    			return arr1[0]-arr2[0];
    			//Ascending order.
    		}
    	});
    	return arr;
    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int ni() {
            return Integer.parseInt(next());
        }

        long nl() {
            return Long.parseLong(next());
        }

        double nd() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

Compilation message

Note: jobs.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	82 ms	10404 KB	Execution failed because the return code was nonzero
2	Runtime error	82 ms	10404 KB	Execution failed because the return code was nonzero
3	Runtime error	81 ms	10360 KB	Execution failed because the return code was nonzero
4	Runtime error	98 ms	10356 KB	Execution failed because the return code was nonzero
5	Runtime error	85 ms	10096 KB	Execution failed because the return code was nonzero
6	Runtime error	89 ms	10488 KB	Execution failed because the return code was nonzero
7	Runtime error	83 ms	10488 KB	Execution failed because the return code was nonzero
8	Runtime error	85 ms	10248 KB	Execution failed because the return code was nonzero
9	Runtime error	86 ms	10228 KB	Execution failed because the return code was nonzero
10	Runtime error	85 ms	10472 KB	Execution failed because the return code was nonzero
11	Runtime error	84 ms	10360 KB	Execution failed because the return code was nonzero
12	Runtime error	85 ms	10356 KB	Execution failed because the return code was nonzero
13	Runtime error	82 ms	10488 KB	Execution failed because the return code was nonzero
14	Runtime error	82 ms	10232 KB	Execution failed because the return code was nonzero
15	Runtime error	87 ms	10356 KB	Execution failed because the return code was nonzero
16	Runtime error	84 ms	10344 KB	Execution failed because the return code was nonzero
17	Runtime error	84 ms	10392 KB	Execution failed because the return code was nonzero
18	Runtime error	84 ms	10488 KB	Execution failed because the return code was nonzero
19	Runtime error	84 ms	10488 KB	Execution failed because the return code was nonzero
20	Runtime error	85 ms	10360 KB	Execution failed because the return code was nonzero