Submission #862104

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
862104	2023-10-17T14:11:10 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++14	90 / 100	358 ms	37016 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	322 ms	4708 KB	Output is correct
2	Correct	339 ms	4744 KB	Output is correct
3	Correct	322 ms	4548 KB	Output is correct
4	Correct	332 ms	4548 KB	Output is correct
5	Correct	327 ms	4548 KB	Output is correct
6	Correct	338 ms	4700 KB	Output is correct
7	Correct	358 ms	4700 KB	Output is correct
8	Correct	347 ms	4548 KB	Output is correct
9	Correct	337 ms	4732 KB	Output is correct
10	Correct	351 ms	5008 KB	Output is correct
11	Correct	28 ms	4784 KB	Output is correct
12	Correct	45 ms	8524 KB	Output is correct
13	Correct	82 ms	15536 KB	Output is correct
14	Correct	100 ms	17580 KB	Output is correct
15	Correct	130 ms	20656 KB	Output is correct
16	Correct	201 ms	25984 KB	Output is correct
17	Correct	190 ms	32152 KB	Output is correct
18	Runtime error	185 ms	34084 KB	Memory limit exceeded
19	Runtime error	287 ms	37016 KB	Memory limit exceeded
20	Correct	182 ms	30688 KB	Output is correct