Submission #1189733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189733		boclobanchat	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	91 ms	20292 KiB

jobs

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
vector<int> vi[MAXN/10],aa[MAXN/10];
int cnt[MAXN];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,d,m;
    cin>>n>>d>>m;
    for(int i=1;i<=m;i++)
    {
    	int res;
    	cin>>res;
    	vi[res].push_back(i);
	}
	int l=1,r=m,ans=0;
	while(l<=r)
	{
		int mid=(l+r)/2,pt=n;
		for(int i=1;i<=n;i++) cnt[i]=vi[i].size();
		for(int i=n;i;i--)
		{
			if(pt>i) break;
			int c=0;
			while(pt>=i-d&&pt>0&&c<mid)
			{
				while(cnt[pt]>0&&c<mid) cnt[pt]--,c++;
				if(cnt[pt]==0) pt--;
			}
		}
		if(!pt) r=mid-1,ans=mid;
		else l=mid+1;
	}
	cout<<ans<<"\n";
	int pt=n;
	for(int i=n;i;i--)
	{
		int c=0;
		while(pt>=i-d&&pt>0&&c<ans)
		{
			while(!vi[pt].empty()&&c<ans) aa[i].push_back(vi[pt][vi[pt].size()-1]),vi[pt].pop_back(),c++;
			if(vi[pt].empty()) pt--;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(auto v:aa[i]) cout<<v<<" ";
		cout<<"0\n";
	}
}

• Subtask 1: 100 / 100