Submission #1328141

#TimeUsernameProblemLanguageResultExecution timeMemory
1328141portajohnJob Scheduling (CEOI12_jobs)C++20
100 / 100
233 ms16528 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
const uint64_t SEED = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        return splitmix64(x + SEED);
    }
};
#define int int64_t
constexpr int INF = INT64_MAX;

bool check(vector<int>& days,int d,int machines) {
	map<int,int> q;
	for (int i = 0; i < days.size(); i++) {
		if (days[i] != 0) {
			q[i] = days[i];
		}
		if (q.empty()) {
			continue;
		}
		int oldest = q.begin()->first;
		int cur_util = 0;
		while (!q.empty() && cur_util < machines) {
			int jobs = min(q[oldest],machines - cur_util);
			cur_util += jobs;
			q[oldest] -= jobs;
			if (q[oldest] == 0) {
				q.erase(oldest);
			}

			oldest = q.begin()->first;
		}
		if (!q.empty() && i - oldest == d) {
			return false;
		}
	}
	return true;
}

int32_t main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	int n,d,m;
	cin >> n >> d >> m;
	vector<int> days(n);
	int r = -INF;
	map<int,queue<int>> q;
	for (int i = 0; i < m; i++) {
		int m_i; cin >> m_i;
		m_i--;
		days[m_i]++;
		q[m_i].push(i + 1);
		r = max(r,days[m_i]);
	}
	int l = 1;
	while (l < r) {
		int m = (l + r) >> 1;
		if (check(days,d,m)) {
			r = m;
		}
		else {
			l = m + 1;
		}
	}
	cout << l << '\n';
	for (int i = 0; i < n; i++) {
		int cur_util = 0;
		int oldest = q.begin()->first;
		while (!q.empty() && cur_util < l) {
			int done = min(l - cur_util,(int64_t) q[oldest].size());
			for (int j = 0; j < done; j++) {
				int job = q[oldest].front();
				q[oldest].pop();
				cout << job << ' ';
			}
			cur_util += done;
			if (q[oldest].empty()) {
				q.erase(oldest);
			}
			oldest = q.begin()->first;
		}
		cout << "0\n";
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...