Submission #118034

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
118034	2019-06-17T18:29:20 Z	Adhyyan1252	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	601 ms	26836 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	3280 KB	Output is correct
2	Correct	30 ms	3280 KB	Output is correct
3	Correct	29 ms	3288 KB	Output is correct
4	Correct	30 ms	3280 KB	Output is correct
5	Correct	30 ms	3284 KB	Output is correct
6	Correct	30 ms	3280 KB	Output is correct
7	Correct	30 ms	3280 KB	Output is correct
8	Correct	30 ms	3320 KB	Output is correct
9	Correct	69 ms	7888 KB	Output is correct
10	Correct	87 ms	7728 KB	Output is correct
11	Correct	44 ms	2940 KB	Output is correct
12	Correct	85 ms	5228 KB	Output is correct
13	Correct	144 ms	9008 KB	Output is correct
14	Correct	297 ms	12100 KB	Output is correct
15	Correct	210 ms	12436 KB	Output is correct
16	Correct	355 ms	15892 KB	Output is correct
17	Correct	461 ms	21300 KB	Output is correct
18	Correct	361 ms	21108 KB	Output is correct
19	Correct	442 ms	26836 KB	Output is correct
20	Correct	601 ms	21424 KB	Output is correct