oj.uz

Submission #50661

# Submission time Handle Problem Language Result Execution time Memory
50661 2018-06-12T10:05:49 Z AryanSM Job Scheduling (CEOI12_jobs) C++17
60 / 100
 678 ms 59548 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];
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<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()
{
	int n;
	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=n;
	//cout<<check(3)<<endl;
	//return 0;
	while(hi>lo+1)
	{
		int mid=(lo+hi)/2;
		if(check(mid,0))hi=mid;
		else lo=mid+1;
		//cerr<<lo<<" "<<hi<<endl;
	}
	//cerr<<"************"<<endl;
	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:55: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:52:6: warning: unused variable 'cnt' [-Wunused-variable]
  int cnt=0;
      ^~~

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 26596 KB Output isn't correct
2 Incorrect 65 ms 26908 KB Output isn't correct
3 Incorrect 64 ms 26908 KB Output isn't correct
4 Incorrect 65 ms 26908 KB Output isn't correct
5 Incorrect 63 ms 26908 KB Output isn't correct
6 Incorrect 64 ms 26908 KB Output isn't correct
7 Incorrect 65 ms 26908 KB Output isn't correct
8 Incorrect 64 ms 26908 KB Output isn't correct
9 Correct 223 ms 28084 KB Output is correct
10 Correct 260 ms 28084 KB Output is correct
11 Correct 80 ms 28084 KB Output is correct
12 Correct 132 ms 31972 KB Output is correct
13 Correct 198 ms 37016 KB Output is correct
14 Correct 282 ms 41344 KB Output is correct
15 Correct 283 ms 43204 KB Output is correct
16 Correct 409 ms 47408 KB Output is correct
17 Correct 489 ms 55280 KB Output is correct
18 Correct 462 ms 56368 KB Output is correct
19 Correct 678 ms 59548 KB Output is correct
20 Correct 514 ms 59548 KB Output is correct