Submission #260650

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
260650	2020-08-10T16:07:12 Z	uacoder123	Job Scheduling (CEOI12_jobs)	C++14	97 / 100	632 ms	23800 KB

jobs

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) lli(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))

typedef int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
int n,m,d;
ii req[10000001];
vi da[100001];
int check(int no)
{
	int cur=1;
	for(int i=0;i<m;++i)
	{
		cur=max(cur,req[i].F);
		while(da[cur].size()>=no)
		{
			cur++;
			if(cur>n)
				return(0);
		}
		if(cur>n)
			return(0);
		if(cur-req[i].F>d)
			return(0);
		else
			da[cur].pb(req[i].S);
	}
}
void cl()
{
	for(int i=0;i<n;++i)
		da[i].clear();
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin>>n>>d>>m;
  for(int i=0;i<m;++i)
  {
  	cin>>req[i].F;
  	req[i].S=i+1;
  }
  sort(req,req+m);
  int l=1,r=m,ans=m;
  while(l<=r)
  {
  	int mi=(l+r)/2;
  	int ch=check(mi);
  	cl();
  	if(ch)
  	{
  		r=mi-1;
  		ans=mi;
  	}
  	else
  		l=mi+1;
  }
  cout<<ans<<endl;
  check(ans);
  for(int i=1;i<=n;++i)
  {
  	for(int j=0;j<da[i].size();++j)
  		cout<<da[i][j]<<' ';
  	cout<<0<<endl;
  }
  return(0);
}

Compilation message

jobs.cpp: In function 'int check(int)':
jobs.cpp:26:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(da[cur].size()>=no)
         ~~~~~~~~~~~~~~^~~~
jobs.cpp: In function 'int main()':
jobs.cpp:74:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<da[i].size();++j)
                ~^~~~~~~~~~~~~
jobs.cpp: In function 'int check(int)':
jobs.cpp:39:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1

97.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	57 ms	4980 KB	Output is correct
2	Correct	56 ms	4980 KB	Output is correct
3	Correct	56 ms	4980 KB	Output is correct
4	Correct	56 ms	4980 KB	Output is correct
5	Correct	56 ms	4980 KB	Output is correct
6	Correct	55 ms	4980 KB	Output is correct
7	Correct	55 ms	4852 KB	Output is correct
8	Correct	57 ms	4980 KB	Output is correct
9	Correct	259 ms	5112 KB	Output is correct
10	Correct	265 ms	5116 KB	Output is correct
11	Correct	47 ms	4984 KB	Output is correct
12	Correct	95 ms	7416 KB	Output is correct
13	Correct	137 ms	10232 KB	Output is correct
14	Correct	209 ms	13264 KB	Output is correct
15	Partially correct	226 ms	14968 KB	Partially correct
16	Correct	299 ms	17768 KB	Output is correct
17	Correct	355 ms	21880 KB	Output is correct
18	Correct	394 ms	21692 KB	Output is correct
19	Correct	632 ms	23800 KB	Output is correct
20	Correct	355 ms	22008 KB	Output is correct