Submission #96296

#	Time	Username	Problem	Language	Result	Execution time	Memory
96296		shoemakerjo	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	968 ms	30584 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

int N, M, D;
const int maxm = 1000010;
const int maxn = 100010;

vector<int> ac[maxn]; //store indices of all that start at me

int ans[maxm];
int st[maxm]; //store start for all values
vector<int> res[maxn];

bool go(int mid) {
	queue<int> q;
	for (int i = 1; i <= N; i++) {
		for (int v : ac[i]) q.push(v);

		for (int j = 1; j <= mid; j++) {
			if (q.empty()) break;
			if (st[q.front()] + D < i)  return false;
			ans[q.front()] = i;
			q.pop();
		}
	}

	return q.size() == 0;

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> D >> M;
	int cur;
	for (int i = 1; i <= M; i++) {
		cin >> cur;
		st[i] = cur;
		ac[cur].push_back(i);
	}

	int lo = 1;
	int hi = M;
	while (lo < hi) {
		int mid = (lo + hi)/2;
		if (go(mid)) {
			hi = mid;
		}
		else lo = mid+1;
	}
	go(lo);
	for (int i = 1; i <= M; i++) {
		res[ans[i]].push_back(i);
	}

	cout << lo << endl;
	for (int i = 1; i <= N; i++) {
		for (int v : res[i]) cout << v << " ";
		cout << 0 << '\n';
	}
	cout.flush();
}

• Subtask 1: 100 / 100