제출 #932937

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
932937		serifefedartar	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	339 ms	29160 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.emplace_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;
	vector<vector<int>> ANS;
	while (R >= L) {
		int mid = L + (R - L) / 2;
		if (check(mid)) {
			ANS = ans;
			res = mid;
			R = mid - 1;
		} else
			L = mid + 1;
	}
	
	cout << res << endl;
	for (auto u : ANS) {
		for (auto v : u)
			cout << v << " ";
		cout << "0" << endl;
	}
}

• Subtask 1: 100 / 100