#include <bits/stdc++.h> using namespace std; // Using int is faster than long long and sufficient for N, M <= 2e9 indices // We only use long long if calculating sums (not needed here) typedef int num; // Global array for the check function to avoid re-allocation overhead // Assuming max M is around 2e5, usually safe to allocate slightly more const int MAX_M = 200005; num finish_times[MAX_M]; int main() { // 1. Ultra-fast I/O ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); num n, d, m; if (!(cin >> n >> d >> m)) return 0; // 2. Store tasks. // We strictly need pairs to track original indices for the final output. vector<pair<num, num>> v(m); for(int i = 0; i < m; i++) { cin >> v[i].first; v[i].second = i; } sort(v.begin(), v.end()); // 3. Binary Search // Lower bound 1, Upper bound M (worst case: all tasks on one day needs M capacity) num ans = m; num low = 1, high = m; while(low <= high) { num k = (low + high) / 2; bool possible = true; // --- THE OPTIMIZATION --- // Instead of simulating days, use the recurrence relation: // Task 'i' reuses the slot of task 'i-k'. // Complexity: Strict O(M) with minimal operations. for(int i = 0; i < m; i++) { num arrival = v[i].first; // If i < k, it's the first task in its "thread", so it finishes at 'arrival'. // If i >= k, it starts after the previous task in this thread finishes (finish_times[i-k] + 1) num prev_finish = (i >= k) ? finish_times[i-k] : 0; // The task finishes at the later of: when it arrives, or when the slot opens up num current_finish = max(arrival, prev_finish + 1); // Check constraints immediately if(current_finish > n || current_finish - arrival > d) { possible = false; break; } finish_times[i] = current_finish; } // ------------------------ if(possible) { ans = k; high = k - 1; } else { low = k + 1; } } cout << ans << "\n"; // 4. Output Logic // The greedy simulation is optimal for printing and runs in O(N + M) // Since we only print once, this is acceptable. num task_idx = 0; for(num day = 1; day <= n; day++) { num capacity = ans; // While tasks are available (arrived <= today) and we have capacity while(capacity > 0 && task_idx < m && v[task_idx].first <= day) { cout << v[task_idx].second + 1 << " "; task_idx++; capacity--; } cout << "0\n"; } return 0; }