oj.uz

답안 #932937

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
932937 2024-02-24T15:06:55 Z serifefedartar Job Scheduling (CEOI12_jobs) C++17
100 / 100
 339 ms 29160 KB 
#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

# 결과 실행 시간 메모리 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