제출 #1294076

#제출 시각아이디문제언어결과실행 시간메모리
1294076harryleeeJob Scheduling (CEOI12_jobs)C++20
100 / 100
104 ms11240 KiB
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
int n, d, m;
vector<int> v[maxn + 1];

bool check(int ma){
	queue<pair<int, int>> q;
	for (int i = 1; i <= n; ++i){
		if (!q.empty() && i - q.front().first > d) return false;
		if (v[i].size() > 0) q.push({i, v[i].size()});
		int cur = ma;
		while(cur > 0 && !q.empty()){
			int lost = min(q.front().second, cur);
			q.front().second -= lost;
			cur -= lost;
			if (q.front().second == 0) q.pop();
		}
	}
	if (q.empty()) return true;
	return false;
}

void print(int ma){
	queue<pair<int, int>> q;
	for (int i = 1; i <= n; ++i){
		if (v[i].size() > 0) q.push({i, 0});
		int cur = ma;
		while(cur > 0 && !q.empty()){
			int j = q.front().second;
			for (; j < min((int)v[q.front().first].size(), q.front().second + cur); ++j)
				cout << v[q.front().first][j] << ' ';
			int lost = min(j - q.front().second, cur);
			q.front().second = j;
			cur -= lost;
			if (q.front().second == v[q.front().first].size()) q.pop();
		}
		cout << 0 << '\n';
	}
	return;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> d >> m;
	for (int i = 1; i <= m; ++i){
		int x; cin >> x;
		v[x].push_back(i);
	}


	int lo = 1, hi = m, ans = -1;
	while(lo <= hi){
		int mid = (lo + hi) >> 1;
		if (check(mid)) ans = mid, hi = mid - 1;
		else lo = mid + 1;
	}

	cout << ans << '\n';
	print(ans);
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...