oj.uz

Submission #843587

# Submission time Handle Problem Language Result Execution time Memory
843587 2023-09-04T07:43:20 Z vjudge1 Job Scheduling (CEOI12_jobs) C++11
0 / 100
 1000 ms 22152 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;
	for(int cnt=1;cnt<=n;++cnt)
	{
		int tmp=m;
		while(tmp--) if(i<a.size())
		{
			if(a[i].num+d<cnt) return false;
			tmp_v.push_back(a[i++].index);
		}
		tmp_v.push_back(0);
	}
	return i>=a.size();
}
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:13:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |   while(tmp--) if(i<a.size())
      |                   ~^~~~~~~~~
jobs.cpp:20:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  return i>=a.size();
      |         ~^~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 833 ms 3656 KB Output isn't correct
2 Incorrect 823 ms 3588 KB Output isn't correct
3 Incorrect 797 ms 3568 KB Output isn't correct
4 Incorrect 670 ms 3768 KB Output isn't correct
5 Incorrect 714 ms 3768 KB Output isn't correct
6 Incorrect 686 ms 3512 KB Output isn't correct
7 Incorrect 666 ms 3768 KB Output isn't correct
8 Incorrect 669 ms 3660 KB Output isn't correct
9 Execution timed out 1020 ms 3536 KB Time limit exceeded
10 Execution timed out 1046 ms 3320 KB Time limit exceeded
11 Incorrect 99 ms 3772 KB Expected EOLN
12 Incorrect 191 ms 6992 KB Expected EOLN
13 Incorrect 291 ms 10412 KB Expected EOLN
14 Execution timed out 1038 ms 10692 KB Time limit exceeded
15 Incorrect 485 ms 17416 KB Output isn't correct
16 Execution timed out 1006 ms 16856 KB Time limit exceeded
17 Execution timed out 1052 ms 19392 KB Time limit exceeded
18 Execution timed out 1020 ms 20160 KB Time limit exceeded
19 Execution timed out 1030 ms 22152 KB Time limit exceeded
20 Execution timed out 1033 ms 19652 KB Time limit exceeded