oj.uz

Submission #978950

# Submission time Handle Problem Language Result Execution time Memory
978950 2024-05-10T04:27:20 Z Amaarsaa Job Scheduling (CEOI12_jobs) C++14
0 / 100
 258 ms 18000 KB 
#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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 4312 KB Expected EOLN
2 Incorrect 22 ms 4312 KB Expected EOLN
3 Incorrect 23 ms 4312 KB Expected EOLN
4 Incorrect 22 ms 4312 KB Expected EOLN
5 Incorrect 22 ms 4312 KB Expected EOLN
6 Incorrect 22 ms 4312 KB Expected EOLN
7 Incorrect 23 ms 4360 KB Expected EOLN
8 Incorrect 22 ms 4312 KB Expected EOLN
9 Incorrect 133 ms 4708 KB Expected EOLN
10 Incorrect 138 ms 4972 KB Expected EOLN
11 Incorrect 13 ms 4440 KB Expected EOLN
12 Incorrect 25 ms 6404 KB Output isn't correct
13 Incorrect 47 ms 9048 KB Expected EOLN
14 Incorrect 78 ms 10484 KB Output isn't correct
15 Incorrect 59 ms 12156 KB Expected EOLN
16 Incorrect 97 ms 14420 KB Expected EOLN
17 Incorrect 114 ms 17744 KB Expected EOLN
18 Incorrect 106 ms 16984 KB Expected EOLN
19 Incorrect 258 ms 18000 KB Expected EOLN
20 Incorrect 113 ms 17640 KB Expected EOLN