Submission #453202

#	Time	Username	Problem	Language	Result	Execution time	Memory
453202		osmanallazov	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	640 ms	13648 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define MAXX 1000005
#define ll long long
pair<int,int>j[MAXX];
int n,m,d;
bool check(int num){
    int cur=0;
    for(int k=0;k<n;k++) {
        for(int i=0;i<num;i++) {
            if(cur<m && j[cur].first<=k+1 && j[cur].first+d>=k+1)cur++;
            else break;
        }
	}
    if(cur==m)return 1;
    else return 0;
}
int main(){
    cin>>n>>d>>m;
    for(int i=0;i<m;i++){
        cin>>j[i].first;
        j[i].second=i+1;
    }
    sort(j,j+m);
    int r=m,l=0,mid,res=-1;
    while(l<=r) {
		mid=(l+r)/2;
		if(check(mid)) {
			res=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	int cur=0;
	cout<<res<<endl;
	for(ll k=0;k<n;k++){
        for(ll i=0;i<res;i++){
           if(cur<m && j[cur].first<=k+1 && j[cur].first+d>=k+1) {
                cout<<j[cur].second<<" ";
                cur++;
            }
            else break;
        }
        cout<<0<<endl;
	}
}

• Subtask 1: 100 / 100