oj.uz

답안 #746534

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
746534 2023-05-22T16:56:10 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
0 / 100
 325 ms 29740 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 == 1) 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 3280 KB Expected EOLN
2 Incorrect 27 ms 3336 KB Expected EOLN
3 Incorrect 28 ms 3352 KB Expected EOLN
4 Incorrect 31 ms 3284 KB Expected EOLN
5 Incorrect 27 ms 3308 KB Expected EOLN
6 Incorrect 27 ms 3280 KB Expected EOLN
7 Incorrect 29 ms 3284 KB Expected EOLN
8 Incorrect 27 ms 3344 KB Expected EOLN
9 Incorrect 59 ms 10868 KB Expected EOLN
10 Incorrect 59 ms 10784 KB Output isn't correct
11 Incorrect 36 ms 2688 KB Output isn't correct
12 Incorrect 69 ms 5292 KB Output isn't correct
13 Incorrect 111 ms 8824 KB Output isn't correct
14 Incorrect 161 ms 11900 KB Output isn't correct
15 Incorrect 175 ms 13368 KB Expected EOLN
16 Incorrect 238 ms 18684 KB Output isn't correct
17 Incorrect 281 ms 22056 KB Output isn't correct
18 Incorrect 309 ms 21016 KB Output isn't correct
19 Incorrect 325 ms 29740 KB Output isn't correct
20 Incorrect 270 ms 22092 KB Output isn't correct