Submission #453059

#	Time	Username	Problem	Language	Result	Execution time	Memory
453059		fuad27	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	607 ms	13904 KiB

jobs

#include<bits/stdc++.h>
using namespace std;
#define MAX (long long)(1e6) + 10
pair<int, int> v[MAX];
int n, d, m;
bool f(int k){
  int p=1;
  for(int i=0;i<m;i+=k){
    for(int y=i;y<i+k&&y<m;y++){
      if(p>v[y].first+d)return 0;
    }
    p++;
  }
  return 1;
}
int main () {
	cin >> n >> d >> m;
	for(int i = 0;i<m;i++) {
		int p;
		cin >> p;
		v[i].first = p;
		v[i].second = i;
	}
	sort(v, v+m);
	int l = 1, r = m;
	int MIN = 1e9;
	while(l <= r) {
		int mid = (l+r)/2;
		if(f(mid)) {
			MIN = min(MIN, mid);
			r = mid-1;
		}
		else {
			l = mid + 1;
		}
	}
	cout<<MIN<<endl;
	for(int i = 0;i<m;i+=MIN) {
		for(int j = i;j<i+MIN and j<m;j++) {
			cout<<v[j].second+1<<' ';
		}
		cout<<0<<"\n";
	}
	for(int i=m/MIN+min(1,m%MIN);i<n;i++){
        	cout<<0<<endl;
      }
}

• Subtask 1: 55 / 100