답안 #260651

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
260651	2020-08-10T16:09:56 Z	uacoder123	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	638 ms	20344 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=1;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

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	56 ms	4724 KB	Output is correct
2	Correct	55 ms	4596 KB	Output is correct
3	Correct	58 ms	4596 KB	Output is correct
4	Correct	56 ms	4604 KB	Output is correct
5	Correct	57 ms	4596 KB	Output is correct
6	Correct	55 ms	4660 KB	Output is correct
7	Correct	55 ms	4596 KB	Output is correct
8	Correct	55 ms	4596 KB	Output is correct
9	Correct	260 ms	4856 KB	Output is correct
10	Correct	260 ms	4856 KB	Output is correct
11	Correct	50 ms	4672 KB	Output is correct
12	Correct	90 ms	6520 KB	Output is correct
13	Correct	140 ms	9080 KB	Output is correct
14	Correct	206 ms	11256 KB	Output is correct
15	Correct	219 ms	12920 KB	Output is correct
16	Correct	288 ms	14860 KB	Output is correct
17	Correct	351 ms	18552 KB	Output is correct
18	Correct	394 ms	18552 KB	Output is correct
19	Correct	638 ms	20344 KB	Output is correct
20	Correct	344 ms	18552 KB	Output is correct