oj.uz

답안 #404952

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
404952 2021-05-15T11:34:40 Z huukhang Job Scheduling (CEOI12_jobs) C++11
100 / 100
 307 ms 17136 KB 
// - Only when necessary :d
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#define fileopen(a, b) freopen(((string)a + ".inp").c_str(), "r", stdin); freopen(((string)b + ".out").c_str(), "w", stdout); 
 
#define ll long long
// #define int long long
#define fi first
#define se second
#define pb push_back
typedef pair<int, int> pii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
const ll mod = 1e9 + 7;
const ll inf = 1e9 + 7;
const double eps = 1e-9;
 
int n, d, m;
pii a[1000005];
int l, r, mid;
int ans;
 
bool check(int x) {
	int res = -inf;
	int j = 1, last = 1;
	for (int i = 1; i <= n; ++i) {
		while (j <= m && a[j].fi <= i && j - last < x) {
			res = max(res, i - a[j].fi);
			++j;
		}
		last = j;
	}
 
	return res <= d;
}
 
void trace(int x) {
	int j = 1, last = 1;
	for (int i = 1; i <= n; ++i) {
		while (j <= m && a[j].fi <= i && j - last < x) {
			cout << a[j].se << " ";
			++j;
		}
		cout << "0\n";
		last = j;
	}
}
 
signed main() {
	#ifdef khangorz
		fileopen("input", "output");
	#endif
	#ifndef khangorz
//		fileopen("LAH", "LAH");
	#endif
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> d >> m;
	for (int i = 1; i <= m; ++i) {
		cin >> a[i].fi;
		a[i].se = i;
	}
	sort(a + 1, a + m + 1);
 
	l = 1; r = 1000000;
	while (l <= r) {
		mid = l + (r - l)/2;

		if (check(mid)) {
			ans = mid;
			r = mid - 1;
		} else l = mid + 1;
	}
 
	cout << ans << "\n";
	trace(ans);
	return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 1988 KB Output is correct
2 Correct 23 ms 1984 KB Output is correct
3 Correct 27 ms 1920 KB Output is correct
4 Correct 23 ms 1892 KB Output is correct
5 Correct 25 ms 1988 KB Output is correct
6 Correct 27 ms 1900 KB Output is correct
7 Correct 23 ms 1872 KB Output is correct
8 Correct 23 ms 1996 KB Output is correct
9 Correct 37 ms 2228 KB Output is correct
10 Correct 38 ms 2116 KB Output is correct
11 Correct 40 ms 2020 KB Output is correct
12 Correct 65 ms 3908 KB Output is correct
13 Correct 96 ms 5776 KB Output is correct
14 Correct 138 ms 8032 KB Output is correct
15 Correct 162 ms 9404 KB Output is correct
16 Correct 205 ms 11924 KB Output is correct
17 Correct 245 ms 13892 KB Output is correct
18 Correct 295 ms 15044 KB Output is correct
19 Correct 307 ms 17136 KB Output is correct
20 Correct 252 ms 13864 KB Output is correct