Submission #932917

#	Time	Username	Problem	Language	Result	Execution time	Memory
932917		serifefedartar	Job Scheduling (CEOI12_jobs)	C++17	30 / 100	239 ms	21624 KiB

jobs

#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define LOGN 20
const ll MOD = 998244353;
const ll MAXN = 1e5 + 100;

int N, D;
vector<vector<int>> ans;
vector<int> days[MAXN];
deque<pair<int,int>> dq;

bool check(int mid) {
	dq = deque<pair<int,int>>();
	ans.clear();
	for (int i = 1; i <= N; i++) {
		ans.push_back(vector<int>());
		for (auto u : days[i]) {
			dq.push_back({i + D, u});
		}

		int Q = mid;
		while (Q && dq.size()) {
			pair<int,int> P = dq.front();
			if (P.f < i)
				return false;
			ans.back().push_back(P.s);
			dq.pop_front();
			Q--;
		}
	}

	return dq.empty();
}

int main() {
	fast
	int M, Q;
	cin >> N >> D >> M;

	for (int i = 0; i < M; i++) {
		cin >> Q;
		days[Q].push_back(i+1);
	}

	int L = 1;
	int R = M;
	int res = -1;
	while (R >= L) {
		int mid = L + (R - L) / 2;
		if (check(mid)) {
			res = mid;
			R = mid - 1;
		} else
			L = mid + 1;
	}
	
	cout << res << "\n";
	for (auto u : ans) {
		for (auto v : u)
			cout << v << " ";
		cout << "0\n";
	}
}

• Subtask 1: 30 / 100