Submission #862104

#	Time	Username	Problem	Language	Result	Execution time	Memory
862104		vjudge1	Job Scheduling (CEOI12_jobs)	C++14	90 / 100	358 ms	37016 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,d,m;
vector<int> a,index_v;
bool is_ok(int machine)
{
//	printf("machine=%d\n",machine);
	int ptr=0;
	for(int day=1;day<=n;++day)
	{
		for(int i=0;i<machine;++i)
		{
//			printf("ptr=%d\n",ptr);
			if(ptr>=a.size()) return true;
			if(a[ptr]>day) break;
			if(a[ptr]+d<day)
			{
//				printf("{%d,%d},FALSE0\n",a[ptr]+d,day);
				return false;
			}
			++ptr;
		}
	}
	return (ptr>=a.size());
}
main()
{
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>d>>m;
	vector<pair<int,int>> tmp(m);
	for(int i=0;i<m;++i) cin>>tmp[i].first,tmp[i].second=i+1;
	sort(tmp.begin(),tmp.end());
	for(auto it:tmp) a.push_back(it.first),index_v.push_back(it.second);
	int l=0,r=1e9,ans=1e9;
	while(l<=r)
	{
		int mid=(r-l)/2+l;
		if(is_ok(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	assert(n*ans>=m);
	cout<<ans<<'\n';
	int ptr=0;
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<ans;++j) if(ptr<index_v.size()) cout<<index_v[ptr]<<' ',++ptr;
		cout<<0<<'\n';
	}
	return 0;
}
/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/

Compilation message (stderr)

jobs.cpp: In function 'bool is_ok(long long int)':
jobs.cpp:15:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |    if(ptr>=a.size()) return true;
      |       ~~~^~~~~~~~~~
jobs.cpp:25:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  return (ptr>=a.size());
      |          ~~~^~~~~~~~~~
jobs.cpp: At global scope:
jobs.cpp:27:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   27 | main()
      | ^~~~
jobs.cpp: In function 'int main()':
jobs.cpp:47:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int j=0;j<ans;++j) if(ptr<index_v.size()) cout<<index_v[ptr]<<' ',++ptr;
      |                             ~~~^~~~~~~~~~~~~~~

• Subtask 1: 90 / 100