Submission #917857

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
917857	2024-01-29T02:10:42 Z	oblantis	Job Scheduling (CEOI12_jobs)	C++17	57 / 100	1000 ms	40536 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[maxn];
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

57.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	1624 KB	Output is correct
2	Correct	13 ms	1372 KB	Output is correct
3	Correct	11 ms	1372 KB	Output is correct
4	Correct	11 ms	1372 KB	Output is correct
5	Correct	11 ms	1368 KB	Output is correct
6	Correct	11 ms	1372 KB	Output is correct
7	Correct	11 ms	1372 KB	Output is correct
8	Correct	10 ms	1372 KB	Output is correct
9	Correct	14 ms	1628 KB	Output is correct
10	Correct	15 ms	1624 KB	Output is correct
11	Correct	11 ms	1372 KB	Output is correct
12	Partially correct	22 ms	2648 KB	Partially correct
13	Execution timed out	1016 ms	40536 KB	Time limit exceeded
14	Runtime error	18 ms	2904 KB	Execution killed with signal 11
15	Runtime error	17 ms	2908 KB	Execution killed with signal 11
16	Runtime error	17 ms	2908 KB	Execution killed with signal 11
17	Runtime error	18 ms	2908 KB	Execution killed with signal 11
18	Runtime error	16 ms	2908 KB	Execution killed with signal 11
19	Runtime error	17 ms	2728 KB	Execution killed with signal 11
20	Runtime error	17 ms	2904 KB	Execution killed with signal 11