Submission #260650

#	Time	Username	Problem	Language	Result	Execution time	Memory
260650		uacoder123	Job Scheduling (CEOI12_jobs)	C++14	97 / 100	632 ms	23800 KiB

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 (stderr)

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 / 100