Submission #118033

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
118033	2019-06-17T18:27:37 Z	Adhyyan1252	Job Scheduling (CEOI12_jobs)	C++11	55 / 100	414 ms	30376 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]){
			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:15:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(pntr < n && sch[pntr].size() >= c){
                      ~~~~~~~~~~~~~~~~~^~~~

Subtask #1

55.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	31 ms	3540 KB	Output isn't correct
2	Incorrect	31 ms	3420 KB	Output isn't correct
3	Incorrect	30 ms	3460 KB	Output isn't correct
4	Incorrect	29 ms	3344 KB	Output isn't correct
5	Incorrect	31 ms	3396 KB	Output isn't correct
6	Incorrect	29 ms	3468 KB	Output isn't correct
7	Incorrect	31 ms	3460 KB	Output isn't correct
8	Incorrect	30 ms	3728 KB	Output isn't correct
9	Correct	48 ms	8156 KB	Output is correct
10	Correct	49 ms	8188 KB	Output is correct
11	Correct	41 ms	3292 KB	Output is correct
12	Correct	81 ms	5976 KB	Output is correct
13	Correct	123 ms	10040 KB	Output is correct
14	Correct	226 ms	13876 KB	Output is correct
15	Incorrect	239 ms	14196 KB	Output isn't correct
16	Correct	320 ms	18712 KB	Output is correct
17	Correct	372 ms	24568 KB	Output is correct
18	Correct	328 ms	24096 KB	Output is correct
19	Correct	414 ms	30376 KB	Output is correct
20	Correct	375 ms	24644 KB	Output is correct