제출 #746190

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
746190		JellyTheOctopus	Job Scheduling (CEOI12_jobs)	C++17	20 / 100	1090 ms	13996 KiB

jobs

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

int N, D, M;
vector<int> arr[100001];

bool check(int x) {
	queue<int> q;
	int wait = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < (int)arr[i].size(); j++) {
			q.push(i);
		}
		if (!q.empty()) {
			wait = max(wait, i-q.front());
		}
		for (int j = 0; j < x && !q.empty(); j++) {
			q.pop();
		}
	}
	return wait <= D;
}

int main() {
	cin >> N >> D >> M;
	for (int i = 1; i <= M; i++) {
		int t;
		cin >> t;
		arr[t].push_back(i);
	}
	int high = N;
	int low = 0;
	while (low < high) {
		int mid = (high+low)/2;
		if (check(mid)) {
			high = mid-1;
		}
		else {
			low = mid;
		}
	}
	int ans = high+1;
	cout << ans << "\n";
	queue<int> q;
	for (int i = 1; i <= N; i++) {
		for (auto v: arr[i]) {
			q.push(v);
		}
		for (int j = 0; j < ans && !q.empty(); j++) {
			cout << q.front() << ' ';
			q.pop();
		}
		cout << 0 << '\n';
	}	
}

• Subtask 1: 20 / 100