Submission #917860

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
917860	2024-01-29T02:13:17 Z	oblantis	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	103 ms	12372 KB

jobs

#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 1e5 + 2;
int cnt[maxn];
int ls[maxn], a[1000000];
void solve() {
	int n, d, m;
	cin >> n >> d >> m;
	for(int i = 0; i < m; i++){
		int x;
		cin >> x;
		a[i] = ls[x];
		ls[x] = i;
		cnt[x]++;
	}
	int l = -1, r = 1000001;
	while(l + 1 < r){
		bool ok = 1;
		int mid = l + (r - l) / 2, xl = 1, ex = 0;
		for(int i = 1; i <= n; i++){
			if(i - xl > d){
				ok = 0;
				break;
			}
			ex += mid;
			while(xl <= i && cnt[xl] <= ex){
				ex -= cnt[xl];
				xl++;
			}
			if(xl > i)ex = 0;
		}
		if(ok)r = mid;
		else l = mid;
	}
	cout << r << '\n';
	int xl = 1, ex = 0;
	for(int i = 1; i <= n; i++){
		ex = r;
		while(ex){
			while(xl <= i && cnt[xl] == 0)xl++;
			if(xl > i)break;
			cout << 1 + ls[xl] << ' ';
			ex--;
			ls[xl] = a[ls[xl]];
			cnt[xl]--;
		}
		cout << "0\n";
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int times = 1;
	//cin >> times;
	for(int i = 1; i <= times; i++) {
		solve();
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	3160 KB	Output is correct
2	Correct	11 ms	3164 KB	Output is correct
3	Correct	11 ms	3416 KB	Output is correct
4	Correct	12 ms	3164 KB	Output is correct
5	Correct	11 ms	3164 KB	Output is correct
6	Correct	11 ms	3164 KB	Output is correct
7	Correct	11 ms	3216 KB	Output is correct
8	Correct	11 ms	3164 KB	Output is correct
9	Correct	14 ms	3420 KB	Output is correct
10	Correct	14 ms	3420 KB	Output is correct
11	Correct	13 ms	3164 KB	Output is correct
12	Correct	22 ms	3924 KB	Output is correct
13	Correct	34 ms	4692 KB	Output is correct
14	Correct	46 ms	5712 KB	Output is correct
15	Correct	55 ms	6392 KB	Output is correct
16	Correct	72 ms	8020 KB	Output is correct
17	Correct	82 ms	9668 KB	Output is correct
18	Correct	91 ms	10580 KB	Output is correct
19	Correct	103 ms	12372 KB	Output is correct
20	Correct	80 ms	9696 KB	Output is correct