Submission #453110

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
453110	2021-08-04T08:04:30 Z	Khizri	Job Scheduling (CEOI12_jobs)	C++17	52 / 100	335 ms	13884 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;
bool check(int k){
	int x=1,say=0;
	for(int i=0;i<m;i++){
		if(arr[i].F>x){
			x=arr[i].F;
			say=1;
		}
		else{
			say++;
			if(x-arr[i].F>d||x>n){
				return false;
			}
		}
		if(say>=k){
			say=0;
			x++;
		}
	}
	return true;
}
void f(int k){
	int x=1,say=0;
	for(int i=0;i<m;i++){
		if(arr[i].F>x){
			for(int j=x;j<arr[i].F;j++){
				cout<<0<<endl;
			}
			x=arr[i].F;
			cout<<arr[i].S<<' ';
		}
		else{
			say++;
			cout<<arr[i].S<<' ';
		}
		if(say>=k){
			say=0;
			x++;
			cout<<0<<endl;
		}
	}
	for(int i=x;i<=n;i++){
		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=1,r=n,ans=1;
	while(l<=r){
		int mm=(l+r)/2;
		if(check(mm)){
			r=mm-1;
			ans=mm;
		}
		else{
			l=mm+1;
		}
	}
	cout<<ans<<endl;
	f(ans);
}
int main(){
	IOS;
	//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Subtask #1

52.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	31 ms	1980 KB	Output isn't correct
2	Incorrect	37 ms	1948 KB	Output isn't correct
3	Incorrect	30 ms	1984 KB	Output isn't correct
4	Incorrect	32 ms	2012 KB	Output isn't correct
5	Incorrect	32 ms	1932 KB	Output isn't correct
6	Incorrect	57 ms	1944 KB	Output isn't correct
7	Incorrect	31 ms	1964 KB	Output isn't correct
8	Incorrect	36 ms	2004 KB	Output isn't correct
9	Correct	40 ms	1992 KB	Output is correct
10	Correct	51 ms	1992 KB	Output is correct
11	Correct	35 ms	1752 KB	Output is correct
12	Correct	68 ms	3260 KB	Output is correct
13	Correct	101 ms	4708 KB	Output is correct
14	Correct	160 ms	6228 KB	Output is correct
15	Incorrect	162 ms	7680 KB	Extra information in the output file
16	Correct	208 ms	9260 KB	Output is correct
17	Correct	245 ms	10660 KB	Output is correct
18	Correct	271 ms	12224 KB	Output is correct
19	Partially correct	335 ms	13884 KB	Partially correct
20	Correct	250 ms	10724 KB	Output is correct