oj.uz

Submission #978945

# Submission time Handle Problem Language Result Execution time Memory
978945 2024-05-10T04:14:02 Z Amaarsaa Job Scheduling (CEOI12_jobs) C++14
0 / 100
 48 ms 65536 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long ;
int a[100004] = {0}, n, d;
queue < 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].front() << " ";
					v[P.first - d].pop();
				}
				s -= P.second;
			}
			else {
				for (int j = 0; j < s; j ++) {
					
					cout << v[P.first - d].front() << " ";
					v[P.first - d].pop();
				}
				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(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 Runtime error 31 ms 65536 KB Execution killed with signal 9
2 Runtime error 31 ms 65536 KB Execution killed with signal 9
3 Runtime error 32 ms 65536 KB Execution killed with signal 9
4 Runtime error 32 ms 65536 KB Execution killed with signal 9
5 Runtime error 32 ms 65536 KB Execution killed with signal 9
6 Runtime error 32 ms 65536 KB Execution killed with signal 9
7 Runtime error 32 ms 65536 KB Execution killed with signal 9
8 Runtime error 29 ms 65536 KB Execution killed with signal 9
9 Runtime error 30 ms 65536 KB Execution killed with signal 9
10 Runtime error 30 ms 65536 KB Execution killed with signal 9
11 Runtime error 48 ms 65536 KB Execution killed with signal 9
12 Runtime error 30 ms 65536 KB Execution killed with signal 9
13 Runtime error 36 ms 65536 KB Execution killed with signal 9
14 Runtime error 45 ms 65536 KB Execution killed with signal 9
15 Runtime error 39 ms 65536 KB Execution killed with signal 9
16 Runtime error 35 ms 65536 KB Execution killed with signal 9
17 Runtime error 36 ms 65536 KB Execution killed with signal 9
18 Runtime error 31 ms 65536 KB Execution killed with signal 9
19 Runtime error 31 ms 65536 KB Execution killed with signal 9
20 Runtime error 31 ms 65536 KB Execution killed with signal 9