oj.uz

Submission #746551

# Submission time Handle Problem Language Result Execution time Memory
746551 2023-05-22T17:59:02 Z hasan_tawsif Job Scheduling (CEOI12_jobs) C++14
0 / 100
 341 ms 30176 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 3600 KB Expected EOLN
2 Incorrect 27 ms 3580 KB Expected EOLN
3 Incorrect 31 ms 3592 KB Expected EOLN
4 Incorrect 28 ms 3700 KB Expected EOLN
5 Incorrect 26 ms 3644 KB Expected EOLN
6 Incorrect 30 ms 3656 KB Expected EOLN
7 Incorrect 29 ms 3664 KB Expected EOLN
8 Incorrect 27 ms 3568 KB Expected EOLN
9 Incorrect 52 ms 11108 KB Expected EOLN
10 Incorrect 57 ms 11208 KB Expected EOLN
11 Incorrect 36 ms 3092 KB Expected EOLN
12 Incorrect 71 ms 5696 KB Expected EOLN
13 Incorrect 105 ms 9032 KB Expected EOLN
14 Incorrect 164 ms 12468 KB Expected EOLN
15 Incorrect 175 ms 13940 KB Expected EOLN
16 Incorrect 233 ms 17944 KB Expected EOLN
17 Incorrect 277 ms 22536 KB Expected EOLN
18 Incorrect 301 ms 21516 KB Expected EOLN
19 Incorrect 341 ms 30176 KB Expected EOLN
20 Incorrect 259 ms 22496 KB Expected EOLN