Submission #978949

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
978949	2024-05-10T04:22:58 Z	Amaarsaa	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	187 ms	17672 KB

jobs

#include<bits/stdc++.h>

using namespace std;
using ll = long long ;
int a[100004] = {0}, n, d;
vector < ll > v[100004];
bool can(int mid) {
	int i, s;
	priority_queue < pair <int,int> , vector<pair<int,int>>, greater<pair<int,int>> > pq;
	for (i = 1; i <= n; i ++) {
		s = mid;
		pq.push({i + d, a[i]});
		while (s > 0) {
			if ( pq.empty()) break;
			pair <int,int> P = pq.top();
			pq.pop();
			if ( P.second < i) return 0;
			if ( s >= P.second) {
				s -= P.second;
			}
			else {
				P.second -= s;
				s= 0;
				pq.push(P);
			}
		}
	}
	if ( pq.empty()) return 1;
	return 0;
} 
void Ans(int mid) {
	int i, s;
	priority_queue < pair <int,int> , vector<pair<int,int>>, greater<pair<int,int>> > pq;
	for (i = 1; i <= n; i ++) {
		s = mid;
		pq.push({i + d, a[i]});
		while (s > 0) {
			if ( pq.empty()) break;
			pair <int,int> P = pq.top();
			pq.pop();
			if ( s >= P.second) {
				for (int j = 0; j < P.second; j ++) {
					
					cout << v[P.first - d].back() << " ";
					v[P.first - d].pop_back();
				}
				s -= P.second;
			}
			else {
				for (int j = 0; j < s; j ++) {
					
					cout << v[P.first - d].back() << " ";
					v[P.first - d].pop_back();
				}
				P.second -= s;
				s = 0;
				pq.push(P);
			}
		}
		cout << "0 " << endl;
	}
	return ;
}
int main() {
//	freopen("moocast.in", "r", stdin);
//	freopen("moocast.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int m, i,x, lo, hi, mid;
	
	cin >> n >> d >> m;
	
	for (i = 1; i <= m; i ++) {
		cin >> x;
		v[x].push_back(i);
		a[x] ++;
	}
	
	lo = 1;
	hi = m; 
	while (lo < hi) {
		mid = (lo + hi)/2;
		if ( can(mid)) lo = mid + 1;
		else hi = mid;
	}
	cout << lo  + 1 << endl;
	Ans(lo + 1);
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	19 ms	4056 KB	Output isn't correct
2	Incorrect	19 ms	4060 KB	Output isn't correct
3	Incorrect	19 ms	4056 KB	Output isn't correct
4	Incorrect	20 ms	4112 KB	Output isn't correct
5	Incorrect	21 ms	4060 KB	Output isn't correct
6	Incorrect	19 ms	4060 KB	Output isn't correct
7	Incorrect	19 ms	4060 KB	Output isn't correct
8	Incorrect	20 ms	4160 KB	Output isn't correct
9	Incorrect	131 ms	5504 KB	Output isn't correct
10	Incorrect	129 ms	5488 KB	Output isn't correct
11	Incorrect	8 ms	4184 KB	Output isn't correct
12	Incorrect	14 ms	5464 KB	Output isn't correct
13	Incorrect	21 ms	8212 KB	Output isn't correct
14	Incorrect	46 ms	10076 KB	Output isn't correct
15	Incorrect	30 ms	10540 KB	Output isn't correct
16	Incorrect	63 ms	13680 KB	Output isn't correct
17	Incorrect	73 ms	16460 KB	Output isn't correct
18	Incorrect	64 ms	15192 KB	Output isn't correct
19	Incorrect	187 ms	17672 KB	Output isn't correct
20	Incorrect	86 ms	16552 KB	Output isn't correct