import java.util.*;
import java.io.*;
public class Main {
// https://oj.uz/problem/view/CEOI12_jobs
public static void main(String[] args) throws IOException, FileNotFoundException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
//BufferedReader in = new BufferedReader(new FileReader("JobScheduling"));
StringTokenizer st = new StringTokenizer(in.readLine());
int n = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] arr = new int[m];
HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
st = new StringTokenizer(in.readLine());
for (int i=0; i<m; ++i) {
arr[i] = Integer.parseInt(st.nextToken());
if (map.containsKey(arr[i])) {
map.get(arr[i]).add(i+1);
}
else {
ArrayList<Integer> c = new ArrayList<>();
c.add(i+1);
map.put(arr[i], c);
}
}
Arrays.parallelSort(arr);
int min=0;
int max=m;
while (min < max) {
int middle = (min + max)/2;
if (check(middle, n, d, map)) {
max = middle;
}
else min = middle+1;
}
System.out.println(min);
// construct
int count=1;
for (int i=0; i<m; i+=min) {
for (int j=i; j<i+min; j++) {
System.out.print(map.get(arr[j]).get(map.get(arr[j]).size()-1) + " ");
map.get(arr[j]).remove(map.get(arr[j]).size()-1);
}
System.out.println(0);
count++;
}
for (int i=count; i<=n; i++) System.out.println(0);
}
public static boolean check(int num, int n, int d, HashMap<Integer, ArrayList<Integer>> map) {
TreeMap<Integer, Integer> cur = new TreeMap<>();
int pointer=1;
while (pointer <= n-d) {
if (map.containsKey(pointer)) {
cur.put(pointer, map.get(pointer).size());
}
else {
}
int curleft = num;
while (cur.size() > 0 && curleft >0) {
int k = cur.firstKey();
if (pointer - k > d) return false;
if (cur.get(k) <= curleft) {
curleft -= cur.get(k);
cur.remove(k);
}
else {
cur.put(k, cur.get(k)-curleft);
curleft=0;
}
}
pointer++;
}
for (int i=0; i<2; i++) {
int curleft = num;
while (cur.size() > 0 && curleft >0) {
int k = cur.firstKey();
if (pointer - k > d) return false;
if (k <= curleft) {
curleft -= k;
cur.remove(k);
}
else {
cur.put(k, cur.get(k)-curleft);
curleft=0;
}
}
}
if (cur.size() > 0) return false;
return true;
}
}
Compilation message
jobs.cpp:1:5: error: 'import' does not name a type
1 | import java.util.*;
| ^~~~~~
jobs.cpp:2:5: error: 'import' does not name a type
2 | import java.io.*;
| ^~~~~~
jobs.cpp:4:5: error: expected unqualified-id before 'public'
4 | public class Main {
| ^~~~~~
