Submission #917849

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
917849	2024-01-29T02:01:32 Z	oblantis	Job Scheduling (CEOI12_jobs)	C++17	7 / 100	1000 ms	45088 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(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(!cnt[xl])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

7.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	10 ms	1368 KB	Output isn't correct
2	Incorrect	11 ms	1372 KB	Output isn't correct
3	Incorrect	14 ms	1372 KB	Output isn't correct
4	Incorrect	10 ms	1460 KB	Output isn't correct
5	Incorrect	11 ms	1368 KB	Output isn't correct
6	Incorrect	10 ms	1368 KB	Output isn't correct
7	Incorrect	11 ms	1368 KB	Output isn't correct
8	Incorrect	12 ms	1372 KB	Output isn't correct
9	Incorrect	12 ms	1628 KB	Output isn't correct
10	Incorrect	13 ms	1628 KB	Output isn't correct
11	Correct	13 ms	1372 KB	Output is correct
12	Partially correct	28 ms	2396 KB	Partially correct
13	Execution timed out	1073 ms	45088 KB	Time limit exceeded
14	Runtime error	17 ms	2904 KB	Execution killed with signal 11
15	Runtime error	16 ms	2908 KB	Execution killed with signal 11
16	Runtime error	18 ms	2744 KB	Execution killed with signal 11
17	Runtime error	17 ms	2908 KB	Execution killed with signal 11
18	Runtime error	16 ms	2908 KB	Execution killed with signal 11
19	Runtime error	16 ms	2904 KB	Execution killed with signal 11
20	Runtime error	17 ms	2908 KB	Execution killed with signal 11