Submission #932937

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
932937	2024-02-24T15:06:55 Z	serifefedartar	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	339 ms	29160 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	6304 KB	Output is correct
2	Correct	36 ms	6484 KB	Output is correct
3	Correct	34 ms	6396 KB	Output is correct
4	Correct	34 ms	6696 KB	Output is correct
5	Correct	34 ms	6496 KB	Output is correct
6	Correct	34 ms	6496 KB	Output is correct
7	Correct	34 ms	6476 KB	Output is correct
8	Correct	34 ms	6668 KB	Output is correct
9	Correct	138 ms	10364 KB	Output is correct
10	Correct	138 ms	10296 KB	Output is correct
11	Correct	25 ms	5212 KB	Output is correct
12	Correct	50 ms	7972 KB	Output is correct
13	Correct	71 ms	11352 KB	Output is correct
14	Correct	133 ms	14480 KB	Output is correct
15	Correct	124 ms	15040 KB	Output is correct
16	Correct	174 ms	18576 KB	Output is correct
17	Correct	214 ms	23952 KB	Output is correct
18	Correct	205 ms	22908 KB	Output is correct
19	Correct	339 ms	29160 KB	Output is correct
20	Correct	227 ms	24116 KB	Output is correct