Submission #387540

#	Time	Username	Problem	Language	Result	Execution time	Memory
387540		ahmet	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	303 ms	23676 KiB

jobs

//https://oj.uz/problem/view/CEOI12_jobs
//https://usaco.guide/silver/binary-search?lang=cpp
#include <bits/stdc++.h>
using namespace std;
#define zaman cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds "
#define rep(i,n) for(long long (i)=0;(i)<(n);++(i))
#define ref(i,a,b) for (long long (i)=(a); (i)<=(b); ++(i))	
#define endl '\n'
#define ll long long
#define pb push_back
#define pii pair<ll,ll>
#define mp make_pair
const int mx=2e5+6;
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n,d,m;cin >> n >> d >> m;
	vector <pair <int,int> > a(m);
	rep(i,m){
		int x;cin >> x;
		a[i]=mp(x,i);
	}
	sort(a.begin(),a.end());
	int l=1,r=1000000;
	while(l<r){
		int mid=(l+r)/2;
		int res=mid;bool ans=true;
		int day=1;
		for(int i=0;i<m;++i){
			int req=a[i].first;
			//if(mid==500000)cout <<i<< " "<<day<< " " <<res<<" "<<req<<endl;
			if(req>day){
				res=mid-1;
				day=req;
				continue;
			}
			if(day>req+d){
				ans=false;
				break;
			}
			--res;
			if(res==0){
				day++;
				res=mid;
			}
		}
		if(ans)r=mid;
		else l=mid+1;
	}

	int cev=l;
	vector <int> b[n+1];
	if(cev){
		int day=1,res=cev;
		for(int i=0;i<m;++i){
			int req=a[i].first;
			if(req>day){
				res=cev-1;
				day=req;
				b[day].pb(a[i].second+1);
				continue;
			}
			--res;
			b[day].pb(a[i].second+1);
			if(res==0){
				day++;
				res=cev;
			}
		}
		cout << cev << endl;
		for(int i=1;i<=n;++i){
			for(int j=0;j<b[i].size();++j){
				cout << b[i][j] << " " ;
			}
			cout<<0<<endl;
		}
	}
	
}	
	

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:6:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define rep(i,n) for(long long (i)=0;(i)<(n);++(i))
      |                                ^
jobs.cpp:18:2: note: in expansion of macro 'rep'
   18 |  rep(i,m){
      |  ^~~
jobs.cpp:71:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |    for(int j=0;j<b[i].size();++j){
      |                ~^~~~~~~~~~~~

• Subtask 1: 100 / 100