oj.uz

Submission #453117

# Submission time Handle Problem Language Result Execution time Memory
453117 2021-08-04T08:07:51 Z fuad27 Job Scheduling (CEOI12_jobs) C++14
100 / 100
 798 ms 17556 KB 
#include <bits/stdc++.h>

using namespace std;
const int max = 1e5+50;

vector<pair<int,int>> j;
vector<int> w;
int n,d,m;
queue<int> tmp;

bool check(int md){
queue<int> q = tmp;
int cur = 1,u = 0;
while(q.size()){
	int v = q.front();
	if(v - d > cur){
		cur = v-d;
		u = 0;
	}
	q.pop();
	if(cur > v)return 0;
	u++;
	if(u == md){
		u = 0;
		cur++;
	}
}
return 1;
}

int main(){
cin >> n >> d >> m;
j.resize(m);
for(int i=0;i<m;i++){
	cin >> j[i].first;
	j[i].second = i;
}
sort(j.begin(),j.end());
for(int i=0;i<m;i++)
	tmp.push(j[i].first + d);
int md,lo=1,hi=1e5,ans=1e5;
while(lo <= hi){
	md = (lo+hi)/2;
	if(check(md)){
		hi = md-1;
		ans = md;
	}else lo = md+1;
}
cout<<ans<<endl;
int u = 0,id=0;
for(int i=0;i<n;i++){
	for(int x=0;x<ans;x++){
		if(id == m)break;
		if(j[id].first - 1 > i)break;
		cout<<j[id].second + 1<<' ';
		id++;			
	}
	cout<<0<<endl;
}
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:50:5: warning: unused variable 'u' [-Wunused-variable]
   50 | int u = 0,id=0;
      |     ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 2288 KB Output is correct
2 Correct 62 ms 2208 KB Output is correct
3 Correct 79 ms 2228 KB Output is correct
4 Correct 83 ms 2228 KB Output is correct
5 Correct 62 ms 2208 KB Output is correct
6 Correct 68 ms 2204 KB Output is correct
7 Correct 61 ms 2212 KB Output is correct
8 Correct 88 ms 2216 KB Output is correct
9 Correct 217 ms 2340 KB Output is correct
10 Correct 227 ms 2348 KB Output is correct
11 Correct 69 ms 2160 KB Output is correct
12 Correct 167 ms 4068 KB Output is correct
13 Correct 230 ms 5960 KB Output is correct
14 Correct 279 ms 7852 KB Output is correct
15 Correct 309 ms 9784 KB Output is correct
16 Correct 399 ms 11652 KB Output is correct
17 Correct 562 ms 13588 KB Output is correct
18 Correct 549 ms 15548 KB Output is correct
19 Correct 798 ms 17556 KB Output is correct
20 Correct 462 ms 13572 KB Output is correct