oj.uz

Submission #842918

# Submission time Handle Problem Language Result Execution time Memory
842918 2023-09-03T13:24:05 Z vjudge1 Job Scheduling (CEOI12_jobs) C++11
0 / 100
 361 ms 28692 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=(r-l)/2+l;
		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 29 ms 3268 KB Output isn't correct
2 Incorrect 33 ms 3260 KB Output isn't correct
3 Incorrect 29 ms 3256 KB Output isn't correct
4 Incorrect 30 ms 3248 KB Output isn't correct
5 Incorrect 30 ms 3256 KB Output isn't correct
6 Incorrect 31 ms 3264 KB Output isn't correct
7 Incorrect 31 ms 3380 KB Output isn't correct
8 Incorrect 28 ms 3260 KB Output isn't correct
9 Incorrect 47 ms 4376 KB Expected EOLN
10 Incorrect 45 ms 4392 KB Expected EOLN
11 Incorrect 34 ms 3188 KB Expected EOLN
12 Incorrect 73 ms 6188 KB Expected EOLN
13 Incorrect 109 ms 9492 KB Expected EOLN
14 Incorrect 170 ms 12424 KB Expected EOLN
15 Incorrect 201 ms 15520 KB Output isn't correct
16 Incorrect 230 ms 19216 KB Expected EOLN
17 Incorrect 295 ms 21776 KB Expected EOLN
18 Incorrect 309 ms 24648 KB Expected EOLN
19 Incorrect 361 ms 28692 KB Expected EOLN
20 Incorrect 275 ms 21724 KB Expected EOLN