Submission #1297804

#TimeUsernameProblemLanguageResultExecution timeMemory
1297804muhammad-ahmadJob Scheduling (CEOI12_jobs)C++20
60 / 100
773 ms28828 KiB
// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include <numeric>
#include <stack>
#include <chrono>
using namespace std;

void fast_io(){
	// freopen("", "r", stdin);
	// freopen("", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(); cout.tie();
	cout << setprecision(9);
}

#define int long long
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second

void print(queue<int> Q){
	while (Q.size()){
		cout << Q.front() << ' ';
		Q.pop();
	}
	cout << endl;
}

void solve() {
	int n, d, m; cin >> m >> d >> n;
	int a[n + 1];
	map<int, int> C;
	
	map<int, vector<int>> idx;
	
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		idx[a[i]].push_back(i);
		C[a[i]]++;
	}
	int l = 0, r = m;
	vector<int> ans;
	while (r - l > 1){
		int mid = (l + r) / 2;
		
		queue<int> Q;
		bool check = 1;
		for (int i = 1; i <= m; i++){
			for (int j = 0; j < C[i]; j++) Q.push({i});
			int x = mid;
			while (x > 0 && Q.size()){
				if (i - Q.front() > d){
					check = 0;
					break;
				}
				x--;
				Q.pop();
			}
		}
		if (check && Q.empty()) {r = mid;}
		else l = mid;
	}	
	
	cout << r << endl;
	queue<int> Q;
	for (int i = 1; i <= m; i++){
		for (int j = 0; j < C[i]; j++) Q.push({i});
		int x = r;
		while (x > 0 && Q.size()){
			x--;
			cout << idx[Q.front()].back() << ' ';
			idx[Q.front()].pop_back();
			Q.pop();
		}
		cout << 0 << endl;
	}
	
	return;
}

signed main() {
    fast_io();
    srand(chrono::steady_clock::now().time_since_epoch().count());
    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
    return 0;
}



#Verdict Execution timeMemoryGrader output
Fetching results...