Submission #978951

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
978951	2024-05-10T04:29:38 Z	Amaarsaa	Job Scheduling (CEOI12_jobs)	C++14	90 / 100	234 ms	18004 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.first < 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   << endl;
	Ans(lo );
}

Subtask #1

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	4312 KB	Output is correct
2	Correct	22 ms	4312 KB	Output is correct
3	Correct	29 ms	4312 KB	Output is correct
4	Correct	29 ms	4312 KB	Output is correct
5	Correct	23 ms	4308 KB	Output is correct
6	Correct	23 ms	4352 KB	Output is correct
7	Correct	22 ms	4308 KB	Output is correct
8	Correct	23 ms	4308 KB	Output is correct
9	Correct	135 ms	4692 KB	Output is correct
10	Correct	143 ms	4944 KB	Output is correct
11	Correct	14 ms	4444 KB	Output is correct
12	Incorrect	29 ms	5980 KB	Output isn't correct
13	Correct	36 ms	9060 KB	Output is correct
14	Incorrect	74 ms	10580 KB	Output isn't correct
15	Correct	68 ms	12044 KB	Output is correct
16	Correct	96 ms	14556 KB	Output is correct
17	Correct	114 ms	17744 KB	Output is correct
18	Correct	106 ms	16992 KB	Output is correct
19	Correct	234 ms	18004 KB	Output is correct
20	Correct	115 ms	17748 KB	Output is correct