oj.uz

Submission #50663

# Submission time Handle Problem Language Result Execution time Memory
50663 2018-06-12T10:19:42 Z AryanSM Job Scheduling (CEOI12_jobs) C++17
100 / 100
 698 ms 59908 KB 
#include<bits/stdc++.h>
using namespace std; 
#define int long long 
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define ld long double
int const M=1e6+10,M2=1e7+10,mod=1e9+7,inf=1e9+10;
int m,d,a[M],n;
vector<int>hlp[M];
vector<pii>all;
bool check(int x,bool ch)
{
	int day=1,cnt=0;
	for(int i=0;i<m;i++)
	{
		if(cnt==x)day++,cnt=0;
		if(day>n)return 0;
		if(day<all[i].F)day=all[i].F,cnt=0;
		if(day>all[i].F+d)return 0;
		if(ch)hlp[day].pb(all[i].S);
		cnt++;
	}
	return 1;
}
int32_t main()
{
	cin>>n>>d>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i];
		all.pb(mp(a[i],i));
	}
	sort(all.begin(),all.end());
	int lo=1,hi=m;
	while(hi>lo+1)
	{
		int mid=(lo+hi)/2;
		if(check(mid,0))hi=mid;
		else lo=mid+1;
	}
	int ans=hi;
	if(check(lo,0))ans=lo;
	check(ans,1);
	cout<<ans<<endl;
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<hlp[i].size();j++)cout<<hlp[i][j]<<" ";
		cout<<0<<endl;
	}
}

Compilation message

jobs.cpp: In function 'int32_t main()':
jobs.cpp:51:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<hlp[i].size();j++)cout<<hlp[i][j]<<" ";
               ~^~~~~~~~~~~~~~
jobs.cpp:48:6: warning: unused variable 'cnt' [-Wunused-variable]
  int cnt=0;
      ^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 28004 KB Output is correct
2 Correct 85 ms 28280 KB Output is correct
3 Correct 75 ms 28280 KB Output is correct
4 Correct 80 ms 28376 KB Output is correct
5 Correct 77 ms 28376 KB Output is correct
6 Correct 77 ms 28376 KB Output is correct
7 Correct 80 ms 28376 KB Output is correct
8 Correct 114 ms 28376 KB Output is correct
9 Correct 210 ms 28376 KB Output is correct
10 Correct 244 ms 28376 KB Output is correct
11 Correct 77 ms 28376 KB Output is correct
12 Correct 129 ms 32140 KB Output is correct
13 Correct 217 ms 37248 KB Output is correct
14 Correct 298 ms 41428 KB Output is correct
15 Correct 292 ms 43344 KB Output is correct
16 Correct 423 ms 47496 KB Output is correct
17 Correct 486 ms 55280 KB Output is correct
18 Correct 507 ms 56500 KB Output is correct
19 Correct 698 ms 59908 KB Output is correct
20 Correct 474 ms 59908 KB Output is correct