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;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1026 ms |
28056 KB |
Time limit exceeded |
2 |
Execution timed out |
1044 ms |
27264 KB |
Time limit exceeded |
3 |
Execution timed out |
1022 ms |
27424 KB |
Time limit exceeded |
4 |
Execution timed out |
1053 ms |
27320 KB |
Time limit exceeded |
5 |
Execution timed out |
1055 ms |
27452 KB |
Time limit exceeded |
6 |
Execution timed out |
1055 ms |
27700 KB |
Time limit exceeded |
7 |
Execution timed out |
1016 ms |
27456 KB |
Time limit exceeded |
8 |
Execution timed out |
1028 ms |
27688 KB |
Time limit exceeded |
9 |
Execution timed out |
1037 ms |
27676 KB |
Time limit exceeded |
10 |
Execution timed out |
1075 ms |
28068 KB |
Time limit exceeded |
11 |
Execution timed out |
1061 ms |
23824 KB |
Time limit exceeded |
12 |
Execution timed out |
1044 ms |
26092 KB |
Time limit exceeded |
13 |
Execution timed out |
1064 ms |
30480 KB |
Time limit exceeded |
14 |
Execution timed out |
1078 ms |
35176 KB |
Time limit exceeded |
15 |
Execution timed out |
1039 ms |
37236 KB |
Time limit exceeded |
16 |
Execution timed out |
1054 ms |
43672 KB |
Time limit exceeded |
17 |
Execution timed out |
1028 ms |
43952 KB |
Time limit exceeded |
18 |
Execution timed out |
1075 ms |
48984 KB |
Time limit exceeded |
19 |
Execution timed out |
1098 ms |
58824 KB |
Time limit exceeded |
20 |
Execution timed out |
1061 ms |
43980 KB |
Time limit exceeded |