oj.uz

Submission #387540

# Submission time Handle Problem Language Result Execution time Memory
387540 2021-04-08T20:28:58 Z ahmet Job Scheduling (CEOI12_jobs) C++14
100 / 100
 303 ms 23676 KB 
//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

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

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2796 KB Output is correct
2 Correct 24 ms 2796 KB Output is correct
3 Correct 24 ms 2796 KB Output is correct
4 Correct 24 ms 2796 KB Output is correct
5 Correct 24 ms 2796 KB Output is correct
6 Correct 24 ms 2796 KB Output is correct
7 Correct 24 ms 2796 KB Output is correct
8 Correct 24 ms 2796 KB Output is correct
9 Correct 40 ms 5100 KB Output is correct
10 Correct 40 ms 5100 KB Output is correct
11 Correct 32 ms 2668 KB Output is correct
12 Correct 66 ms 4972 KB Output is correct
13 Correct 96 ms 7916 KB Output is correct
14 Correct 140 ms 10988 KB Output is correct
15 Correct 161 ms 11628 KB Output is correct
16 Correct 200 ms 14956 KB Output is correct
17 Correct 239 ms 19308 KB Output is correct
18 Correct 268 ms 19692 KB Output is correct
19 Correct 303 ms 23676 KB Output is correct
20 Correct 237 ms 19464 KB Output is correct