Submission #1340192

#TimeUsernameProblemLanguageResultExecution timeMemory
1340192fatime_aslan_156Job Scheduling (CEOI12_jobs)C++20
100 / 100
276 ms25064 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n,d,m,z=0;
	cin>>n>>d>>m;
	map<ll,ll>c;
	set<ll>e;
	vector<ll>v(m);
	vector<vector<ll>>o(n+1);
	for(int i=0; i<m; i++)
	{
		cin>>v[i];
		o[v[i]].push_back(i+1);
		e.insert(v[i]);
		c[v[i]]++;
		z=max(z,c[v[i]]);
	}
	ll l=1,r=m,k=m;
	while(l<=r)
	{
		ll mi=(l+r)>>1,er=0;
		ll w=0,p=1;
		bool h=0;
		for(int i:e)
		{
			if(p>n)
				break;
			for(int j=0; j<o[i].size(); j++)
			{
			    if(p>n)
			    {
			        h=1;
			        break;
			    }
			    if(i+d<p)
			    {
			        h=1;
			        break;
			    }
				if(i>p)
				{
					j--;
					p++;
					w=0;
					continue;
				}
				else if(w==mi)
				{
					j--;
					p++;
					w=0;
				}
				else
				{
					er++;
					w++;
				}
			}
			if(h)
			break;
		}
		if(er==m)
		{
			k=mi;
			r=mi-1;
		}
		else
			l=mi+1;
	}
	cout<<k<<endl;
	ll w=0,p=0;
	bool q=0;
	for(int i:e)
	{
		for(int j=0; j<o[i].size(); j++)
		{
			if(i>p+1)
			{
				cout<<0<<endl;
				j--;
				p++;
				w=0;
				q=0;
			}
			else if(w==k)
			{
				cout<<0<<endl;
				q=0;
				j--;
				p++;
				w=0;
			}
			else
			{
				cout<<o[i][j]<<' ';
				q=1;
				w++;
			}
		}
	}
	if(q)
	{
		p++;
		cout<<0<<endl;
	}
	for(int i=p; i<n; i++)
		cout<<0<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...