제출 #1328135

#제출 시각아이디문제언어결과실행 시간메모리
1328135portajohnJob Scheduling (CEOI12_jobs)C++20
40 / 100
75 ms12276 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;
	queue<int> jobs;
	for (int i = 0; i < m; i++) {
		int m_i; cin >> m_i;
		jobs.push(m_i);
		m_i--;
		days[m_i]++;
		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';
	int q = 0;
	for (int i = 0; i < n; i++) {
		q += days[i];
		int done = min(q,l);
		for (int j = 0; j < done; j++) {
			cout << jobs.front() << ' ';
			jobs.pop();
		}
		q -= done;
		cout << "0\n";
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...