oj.uz

Submission #842906

# Submission time Handle Problem Language Result Execution time Memory
842906 2023-09-03T13:11:38 Z vjudge1 Job Scheduling (CEOI12_jobs) C++11
0 / 100
 370 ms 32272 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 3772 KB Output isn't correct
2 Incorrect 30 ms 3788 KB Output isn't correct
3 Incorrect 31 ms 3620 KB Output isn't correct
4 Incorrect 29 ms 3772 KB Output isn't correct
5 Incorrect 30 ms 3664 KB Output isn't correct
6 Incorrect 28 ms 3772 KB Output isn't correct
7 Incorrect 28 ms 3772 KB Output isn't correct
8 Incorrect 28 ms 3772 KB Output isn't correct
9 Incorrect 43 ms 4476 KB Expected EOLN
10 Incorrect 43 ms 4536 KB Expected EOLN
11 Incorrect 35 ms 3680 KB Expected EOLN
12 Incorrect 75 ms 7084 KB Expected EOLN
13 Incorrect 107 ms 10400 KB Expected EOLN
14 Incorrect 159 ms 14392 KB Expected EOLN
15 Incorrect 188 ms 17268 KB Output isn't correct
16 Incorrect 233 ms 23016 KB Expected EOLN
17 Incorrect 345 ms 25156 KB Expected EOLN
18 Incorrect 302 ms 27980 KB Expected EOLN
19 Incorrect 370 ms 32272 KB Expected EOLN
20 Incorrect 277 ms 26200 KB Expected EOLN