oj.uz

Submission #50662

# Submission time Handle Problem Language Result Execution time Memory
50662 2018-06-12T10:12:09 Z AryanSM Job Scheduling (CEOI12_jobs) C++17
60 / 100
 673 ms 59732 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=n;
	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
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 26596 KB Output isn't correct
2 Incorrect 64 ms 26780 KB Output isn't correct
3 Incorrect 64 ms 26780 KB Output isn't correct
4 Incorrect 65 ms 26780 KB Output isn't correct
5 Incorrect 64 ms 26780 KB Output isn't correct
6 Incorrect 68 ms 26792 KB Output isn't correct
7 Incorrect 65 ms 26800 KB Output isn't correct
8 Incorrect 63 ms 26856 KB Output isn't correct
9 Correct 212 ms 28264 KB Output is correct
10 Correct 222 ms 28264 KB Output is correct
11 Correct 75 ms 28264 KB Output is correct
12 Correct 144 ms 32140 KB Output is correct
13 Correct 183 ms 37228 KB Output is correct
14 Correct 292 ms 41376 KB Output is correct
15 Correct 288 ms 43268 KB Output is correct
16 Correct 416 ms 47472 KB Output is correct
17 Correct 502 ms 55284 KB Output is correct
18 Correct 534 ms 56604 KB Output is correct
19 Correct 673 ms 59732 KB Output is correct
20 Correct 515 ms 59732 KB Output is correct