Submission #917846

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
917846	2024-01-29T01:59:35 Z	oblantis	Job Scheduling (CEOI12_jobs)	C++17	17 / 100	1000 ms	42000 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 <= n && 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 <= n && 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

17.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	11 ms	1372 KB	Output isn't correct
2	Incorrect	15 ms	1368 KB	Output isn't correct
3	Incorrect	12 ms	1372 KB	Output isn't correct
4	Incorrect	15 ms	1368 KB	Output isn't correct
5	Incorrect	11 ms	1368 KB	Output isn't correct
6	Incorrect	11 ms	1316 KB	Output isn't correct
7	Incorrect	11 ms	1372 KB	Output isn't correct
8	Incorrect	11 ms	1372 KB	Output isn't correct
9	Correct	14 ms	1624 KB	Output is correct
10	Correct	14 ms	1624 KB	Output is correct
11	Correct	11 ms	1368 KB	Output is correct
12	Partially correct	22 ms	2388 KB	Partially correct
13	Execution timed out	1014 ms	42000 KB	Time limit exceeded
14	Runtime error	18 ms	2904 KB	Execution killed with signal 11
15	Runtime error	17 ms	2904 KB	Execution killed with signal 11
16	Runtime error	18 ms	2876 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	16 ms	2856 KB	Execution killed with signal 11
20	Runtime error	24 ms	2776 KB	Execution killed with signal 11