oj.uz

Submission #306556

# Submission time Handle Problem Language Result Execution time Memory
306556 2020-09-25T20:26:24 Z updown1 Job Scheduling (CEOI12_jobs) Java 11
0 / 100
 1000 ms 65556 KB 
import java.util.*;
import java.io.*;
 
public class jobs {
 
    static pair[] inp;
    static int N, D, M;
	// TLE && RTE
	public static void main(String[] args) throws IOException, FileNotFoundException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		//BufferedReader in = new BufferedReader(new FileReader("test.in"));
 
		StringTokenizer st = new StringTokenizer(in.readLine());
		M = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
 
		inp = new pair[N];
		st = new StringTokenizer(in.readLine());
		for (int i=0; i<N; ++i) {
			inp[i] = new pair(Integer.parseInt(st.nextToken()), i+1);
		}
		Arrays.sort(inp);
		int a=1, b=N;
        while (a != b) {
            int mid = (a+b)/2;
            if (works(mid)) b = mid;
            else a = mid+1;
        }
        System.out.println(a);
        int at = 0;
        for (int j=0; j<M; j++) {
            int cnt = 0;
            while (at != N && inp[at].val <= j && cnt <a) {
                cnt++;
                System.out.print(inp[at].index + " ");
                at++;
            }
            System.out.println(0);
        }
 
	}
 
	public static boolean works(int m) {
		int day = 1;
        int lef = m;
        for (int i=0; i<N; i++) {
            if (inp[i].val > day) {day=inp[i].val; lef = m;}
            if (inp[i].val + D < day) return false;
            lef--;
            if (lef == 0) {day++; lef=m;}
        }
        return true;
	}
 
	public static class pair implements Comparable<pair> {
        public int val, index;
        public pair(int a, int b) {
            this.val = a;
            this.index = b;
        }
        @Override
        public int compareTo(pair other) {
          return val - other.val;
        }
 
	}
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 979 ms 48320 KB Memory limit exceeded
2 Runtime error 929 ms 44808 KB Memory limit exceeded
3 Runtime error 957 ms 47256 KB Memory limit exceeded
4 Execution timed out 1059 ms 50648 KB Time limit exceeded
5 Runtime error 938 ms 48876 KB Memory limit exceeded
6 Runtime error 896 ms 45544 KB Memory limit exceeded
7 Runtime error 971 ms 48768 KB Memory limit exceeded
8 Runtime error 908 ms 46456 KB Memory limit exceeded
9 Execution timed out 1123 ms 48448 KB Time limit exceeded
10 Execution timed out 1084 ms 49616 KB Time limit exceeded
11 Execution timed out 1012 ms 43116 KB Time limit exceeded
12 Execution timed out 1035 ms 40192 KB Time limit exceeded
13 Execution timed out 1080 ms 63000 KB Time limit exceeded
14 Execution timed out 1082 ms 64180 KB Time limit exceeded
15 Execution timed out 1043 ms 64876 KB Time limit exceeded
16 Runtime error 1070 ms 65544 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 418 ms 65548 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 398 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 405 ms 65556 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 403 ms 65556 KB Execution killed with signal 9 (could be triggered by violating memory limits)