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
#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;
}
# 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