Submission #453162

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
453162	2021-08-04T08:27:37 Z	Khizri	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	316 ms	16232 KB

jobs

#include <bits/stdc++.h>
using namespace std;
//------------------------------DEFINE------------------------------
//******************************************************************
#define IOS ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0)
#define ll long long
#define pb push_back		 
#define F first																 
#define S second 															 
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
#define endl "\n"
//******************************************************************
//----------------------------FUNCTION------------------------------
//******************************************************************
ll gcd(ll a,ll b){
	if(a>b) swap(a,b);
	if(a==0) return a+b;
	return gcd(b%a,a);
}
ll lcm(ll a,ll b){
	return a/gcd(a,b)*b;
}
bool is_prime(ll n){
	ll k=sqrt(n);
	if(n==2) return true;
	if(n<2||n%2==0||k*k==n) return false;
	for(int i=3;i<=k;i+=2){
		if(n%i==0){
			return false;
		}
	}
	return true;
}
//*****************************************************************
//--------------------------MAIN-CODE------------------------------
const int mxn=1e6+5;
int t=1,n,d,m;
vector<pii>arr;
vector<int>vt[100005];
bool check(int k){
	int x=1,say=0;
	for(int i=0;i<arr.size();i++){
		if(arr[i].F>x){
			x=arr[i].F;
			say=1;
		}
		else{
			say++;
			if(x-arr[i].F>d){
				return false;
			}
		}
		if(say>=k){
			say=0;
			x++;
		}
	}
	return true;
}
void f(int k){
	int say=0,ind=0;
	for(int x=1;x<=n;x++){
		say=0;
		while(ind<m&&arr[ind].F<=x&&say<k){
			cout<<arr[ind].S<<' ';
			ind++;
			say++;
		}
		cout<<0<<endl;
	}
}
void solve(){
	cin>>n>>d>>m;
	for(int i=1;i<=m;i++){
		int q;
		cin>>q;
		arr.pb({q,i});
	}
	sort(all(arr));
	int l=0,r=n,ans=10000000;
	while(l<=r){
		int mm=(l+r)/2;
		if(check(mm)){
			r=mm-1;
			ans=min(ans,mm);
		}
		else{
			l=mm+1;
		}
	}
	cout<<ans<<endl;
	f(ans);
}
int main(){
	IOS;
	//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Compilation message

jobs.cpp: In function 'bool check(int)':
jobs.cpp:48: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]
   48 |  for(int i=0;i<arr.size();i++){
      |              ~^~~~~~~~~~~

Subtask #1

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	25 ms	4168 KB	Output isn't correct
2	Incorrect	25 ms	4160 KB	Output isn't correct
3	Incorrect	25 ms	4168 KB	Output isn't correct
4	Incorrect	25 ms	4176 KB	Output isn't correct
5	Incorrect	25 ms	4092 KB	Output isn't correct
6	Incorrect	25 ms	4168 KB	Output isn't correct
7	Incorrect	27 ms	4100 KB	Output isn't correct
8	Incorrect	28 ms	4092 KB	Output isn't correct
9	Correct	41 ms	4352 KB	Output is correct
10	Correct	45 ms	4416 KB	Output is correct
11	Correct	35 ms	4140 KB	Output is correct
12	Correct	64 ms	5652 KB	Output is correct
13	Correct	97 ms	7168 KB	Output is correct
14	Correct	139 ms	8624 KB	Output is correct
15	Correct	166 ms	10028 KB	Output is correct
16	Correct	213 ms	11616 KB	Output is correct
17	Correct	258 ms	13012 KB	Output is correct
18	Correct	272 ms	14560 KB	Output is correct
19	Correct	316 ms	16232 KB	Output is correct
20	Correct	236 ms	13064 KB	Output is correct