Submission #842906

#	Time	Username	Problem	Language	Result	Execution time	Memory
842906		vjudge1	Job Scheduling (CEOI12_jobs)	C++11	0 / 100	370 ms	32272 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define num first
#define index second
vector<int> tmp_v;
bool is_ok(vector<pair<int,int>> a,int m,int d,int n)
{
	tmp_v.clear();
	int i=0,cnt_day=1;
	while(i<a.size())
	{
//		printf("cnt_day=%d,m=%d,n=%d\n",cnt_day,m,n);
		int tmp=m;
		while(tmp&&i<a.size())
		{
			if(a[i].num+d<cnt_day||cnt_day>n) return false;
			tmp_v.push_back(a[i].index),--tmp,++i;
		}
		tmp_v.push_back(0);
		++cnt_day;
	}
	if(i<a.size()) return false;
	while(cnt_day<=n) ++cnt_day,tmp_v.push_back(0);
//	printf("i=%d\n",i);
	return true;
}
int main()
{
	int n,d,m;
	cin>>n>>d>>m;
	vector<pair<int,int>> a(m);
	vector<int> ans_v;
	for(int i=0;i<m;++i) cin>>a[i].num,a[i].index=i+1;
	sort(a.begin(),a.end());
//	for(auto it:a) cout<<it.num<<' '<<it.index<<'\n';
	int l=1,r=m,ans=m;
	while(l<=r)
	{
		int mid=(l-r)/2+r;
		if(is_ok(a,mid,d,n)) ans_v=tmp_v,ans=mid,r=mid-1;
		else l=mid+1;
	}
	cout<<ans<<'\n';
	for(auto it:ans_v)
	{
		cout<<it<<' ';
		if(it==0) cout<<'\n';
	}
	return 0;
}
/*
8 2 12
1 1 2 2 2 3 3 4 4 5 6 6

8 2 12
1 2 4 2 1 3 5 6 2 3 6 4

2
5 1 0
9 4 0
2 10 0
6 12 0
3 7 0
11 8 0
0
0
*/

Compilation message (stderr)

jobs.cpp: In function 'bool is_ok(std::vector<std::pair<int, int> >, int, int, int)':
jobs.cpp:10:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  while(i<a.size())
      |        ~^~~~~~~~~
jobs.cpp:14:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   while(tmp&&i<a.size())
      |              ~^~~~~~~~~
jobs.cpp:22:6: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  if(i<a.size()) return false;
      |     ~^~~~~~~~~

• Subtask 1: 0 / 100