Submission #1277628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277628		random_name	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	196 ms	18076 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
	ll n,d,m; cin>>n>>d>>m;
	vector<vector<ll>> J(n);
	for(ll i=0;i<m;i++){
		ll a;cin>>a;
		J[a-1].push_back(i);
	}

	ll l=1,r=m;
	while(l<r){
		ll mid=(l+r)/2;
		bool able=true;
		queue<pair<ll, ll>> q;
		for(ll i=0;i<n;i++){
			q.push({i, J[i].size()});

			if(q.front().first + d < i){
				able = false;
				break;
			}
			
			ll diff = mid;
			while(!q.empty() && diff > 0){
				if(q.front().second <= diff){
					diff -= q.front().second;
					q.pop();
				}

				else{
					q.front().second -= diff;
					diff = 0;
				}
			}
		}

		// if(q.size() != 0){
		// 	able = false;
		// }

		if(able){
			r = mid;
		}

		else
			l = mid+1;
	}

	cout << l << '\n';

	queue<pair<ll, ll>> q;
	for(ll i=0;i<n;i++){
		q.push({i, J[i].size()});
		
		ll diff = l;
		while(!q.empty() && diff > 0){
			if(q.front().second <= diff){
				diff -= q.front().second;
				for(ll j=0;j<q.front().second;j++){
					cout << J[q.front().first].back()+1 << ' ';
					J[q.front().first].pop_back();
				}
				q.pop();
			}

			else{
				for(ll j=0;j<diff;j++){
					cout << J[q.front().first].back()+1 << ' ';
					J[q.front().first].pop_back();
				}

				q.front().second -= diff;
				diff = 0;
			}
		}

		cout << 0 << '\n';
	}
}

• Subtask 1: 100 / 100