oj.uz

Submission #746552

# Submission time Handle Problem Language Result Execution time Memory
746552 2023-05-22T18:00:50 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
0 / 100
 342 ms 29772 KB 
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

void solve() {
	int n, d, m; cin >> n >> d >> m;
	vector<pair<int, int > > v;
	for (int i = 0; i < m; ++i) {
		int x; cin >> x;
		v.push_back({x, i + 1});
	}
	sort(v.begin(), v.end());
	// for (auto [u, x] : v) cerr << u << " " << x << endl;
	// cerr << "----------------------------------------------\n";
	int lo = 1, hi = m;
	vector<int> ans[n + 1], final[n + 1];
	auto test = [&] (int numOfMachine) {
		for (int i = 1; i <= n; ++i) ans[i].clear();
		int cur = 0, tot = 0, day = 0;
		for (int i = 0; i < m; ) {
			int j = i;
			if (day < v[i].first) cur = 0;
			day = max(day, v[i].first);
			while (j < m and v[i].first == v[j].first) {
				if (day - v[j].first > d) return false;
				ans[day].push_back(v[j].second);
				cur++;
				tot++;
				j++;
	//			if (numOfMachine == 2) cerr << "#" << day << " " << tot << " " << cur << endl;
				if (cur == numOfMachine) cur = 0, day++;
			}
			i = j;
		}
		return tot == m;
	};
	while (lo < hi) {
		int mid = lo + (hi - lo) / 2;
		if (test(mid)) {
			hi = mid;
			for (int i = 1; i <= n; ++i) {
				final[i].clear();
				for (auto u : ans[i]) final[i].push_back(u);
				final[i].push_back(0);
			}
		}
		else lo = mid + 1;
	}
	cout << hi << "\n";
	for (int i = 1; i <= n; ++i) {
		for (auto u : final[i]) cout << u << " ";
		cout << "\n";
	}
} 

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1; 
//    cin >> t;
    while(t--) solve();
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 3280 KB Expected EOLN
2 Incorrect 26 ms 3308 KB Expected EOLN
3 Incorrect 25 ms 3276 KB Expected EOLN
4 Incorrect 25 ms 3268 KB Expected EOLN
5 Incorrect 25 ms 3280 KB Expected EOLN
6 Incorrect 26 ms 3280 KB Expected EOLN
7 Incorrect 26 ms 3324 KB Expected EOLN
8 Incorrect 26 ms 3292 KB Expected EOLN
9 Incorrect 52 ms 10868 KB Expected EOLN
10 Incorrect 55 ms 10928 KB Expected EOLN
11 Incorrect 35 ms 2792 KB Expected EOLN
12 Incorrect 75 ms 5208 KB Expected EOLN
13 Incorrect 105 ms 8712 KB Expected EOLN
14 Incorrect 139 ms 11960 KB Expected EOLN
15 Incorrect 169 ms 13572 KB Expected EOLN
16 Incorrect 212 ms 17432 KB Expected EOLN
17 Incorrect 257 ms 21932 KB Expected EOLN
18 Incorrect 282 ms 20936 KB Expected EOLN
19 Incorrect 342 ms 29772 KB Expected EOLN
20 Incorrect 251 ms 21996 KB Expected EOLN