Submission #118034

#	Time	Username	Problem	Language	Result	Execution time	Memory
118034		Adhyyan1252	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	601 ms	26836 KiB

jobs

#include<bits/stdc++.h>

using namespace std;
//11 37
int n, d, m;
vector<pair<int, int> > a;
vector<vector<int> > g;

bool pos(int c, vector<vector<int> >& sch){
	//is it poss to do it with c machines
	sch.resize(n);
	int pntr = 0;
	for(int i = 0; i < n; i++){
		for(int j : g[i]){
			pntr = max(pntr, i);
			while(pntr < n && sch[pntr].size() >= c){
				pntr++;
			}
			if(pntr > i + d) return false;	
			sch[pntr].push_back(j);
		}
	}
	return true;
}


int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>d>>m;
	a.resize(m);
	g.resize(n);
	for(int i = 0; i < m; i++){
		cin>>a[i].first; a[i].first--;
		a[i].second = i;
		g[a[i].first].push_back(i);
	}
	sort(a.begin(), a.end());
	int low = 1, high = m, mid;
	while(low < high){
		mid = (low + high)/2;
		//check if it is possible to do it with mid number of computers
		vector<vector<int> > sch;
		bool check = pos(mid, sch);
		if(check){
			high = mid;
		}else{
			low = mid+1;
		}
	}
	mid = (low + high)/2;
	vector<vector<int> > sch;
	pos(mid, sch);
	cout<<mid<<endl;
	for(int i = 0; i < n; i++){
		for(int j: sch[i]){
			cout<<j+1<<" ";
		}
		cout<<0<<"\n";
	}
	cout.flush();
}

Compilation message (stderr)

jobs.cpp: In function 'bool pos(int, std::vector<std::vector<int> >&)':
jobs.cpp:16:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(pntr < n && sch[pntr].size() >= c){
                      ~~~~~~~~~~~~~~~~~^~~~

• Subtask 1: 100 / 100