Submission #1261575

#TimeUsernameProblemLanguageResultExecution timeMemory
1261575PokemonMasterJob Scheduling (CEOI12_jobs)C++20
100 / 100
247 ms27844 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
	ios::sync_with_stdio(0);//bekten topchik
	int n,d,m;
	cin>>n>>d>>m;
	vector <int> x(m+1);
	for(int i=1;i<=m;i++)cin>>x[i];
	vector <array <int,2> > a(m+1);
	for(int i=1;i<=m;i++)a[i][0]=x[i];
	for(int i=1;i<=m;i++)a[i][1]=i;
	sort(a.begin()+1,a.end());
	int l=0,r=m+1;
	while(r-l>1)
	{
		int bad=0;
		int mid=(l+r)/2,pt=1;
		for(int day=1;day<=n;day++)
		{
			for(int i=1;i<=mid && pt<=m;i++)
			{
				if(a[pt][0]+d<day)bad=1;
				if(a[pt][0]>day)break;
				pt++;
			}
		}
		if(pt-m-1)bad=1;
		if(bad)
		{
			l=mid;
		}else
		{
			r=mid;
		}
	}
	int pt=1;
	cout<<r<<endl;
	for(int day=1;day<=n;day++)
	{
		for(int i=1;i<=r && pt<=m;i++)
		{
			if(a[pt][0]>day)break;
			cout<<a[pt][1]<<' ';
			pt++;
		}
		cout<<0<<endl;
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...