Submission #917854

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
917854	2024-01-29T02:06:35 Z	oblantis	Job Scheduling (CEOI12_jobs)	C++17	7 / 100	1000 ms	43328 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(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

7.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	15 ms	1288 KB	Output isn't correct
2	Incorrect	10 ms	1368 KB	Output isn't correct
3	Incorrect	12 ms	1368 KB	Output isn't correct
4	Incorrect	10 ms	1372 KB	Output isn't correct
5	Incorrect	11 ms	1372 KB	Output isn't correct
6	Incorrect	12 ms	1372 KB	Output isn't correct
7	Incorrect	11 ms	1368 KB	Output isn't correct
8	Incorrect	11 ms	1320 KB	Output isn't correct
9	Incorrect	13 ms	1628 KB	Output isn't correct
10	Incorrect	13 ms	1624 KB	Output isn't correct
11	Correct	12 ms	1372 KB	Output is correct
12	Partially correct	22 ms	2348 KB	Partially correct
13	Execution timed out	1047 ms	43328 KB	Time limit exceeded
14	Runtime error	19 ms	2928 KB	Execution killed with signal 11
15	Runtime error	17 ms	2908 KB	Execution killed with signal 11
16	Runtime error	18 ms	2952 KB	Execution killed with signal 11
17	Runtime error	18 ms	2908 KB	Execution killed with signal 11
18	Runtime error	17 ms	2908 KB	Execution killed with signal 11
19	Runtime error	19 ms	2944 KB	Execution killed with signal 11
20	Runtime error	18 ms	2908 KB	Execution killed with signal 11