Submission #1261567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261567		PokemonMaster	Job Scheduling (CEOI12_jobs)	C++20	80 / 100	567 ms	42584 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
	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;
		queue <pair <int,int> > q;
		for(int i=1;i<=m;i++)q.push({a[i][0],a[i][1]});
		int mid=(l+r)/2;
		for(int day=1;day<=n;day++)
		{
			for(int i=1;i<=mid && q.size();i++)
			{
				pair <int,int> v=q.front();
				if(v.first+d<day)bad=1;
				if(v.first>day)break;
				q.pop();
			}
		}
		if(q.size())bad=1;
		if(bad)
		{
			l=mid;
		}else
		{
			r=mid;
		}
	}
	cout<<r<<endl;
	queue <pair <int,int> > q;
	for(int i=1;i<=m;i++)q.push({a[i][0],a[i][1]});
	for(int day=1;day<=n;day++)
	{
		for(int i=1;i<=r && q.size();i++)
		{
			pair <int,int> v=q.front();
			if(v.first>day)break;
			cout<<v.second<<' ';
			q.pop();
		}
		cout<<0<<endl;
	}
	
}

• Subtask 1: 80 / 100