Submission #446570

#	Time	Username	Problem	Language	Result	Execution time	Memory
446570		ArianKheirandish	Job Scheduling (CEOI12_jobs)	C++17	25 / 100	1096 ms	29040 KiB

jobs

//in the name of god//

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _			ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define all(x)		x.begin(),x.end()
#define F			first
#define S			second
#define MP			make_pair

const int maxn = 1e6 + 10;
const int LG = 30;
const ll Inf = 1e9;
int n, d, m;
pair<int, int> a[maxn];

bool check(int x){
	int now = 1;
	int z = 0;
	for(int i = 0 ; i < m ; i ++){
		if(a[i].F > now)
			now = a[i].F,
			z = 1;
		
		else if(a[i].F < now - d)
			return 0;
			
		else if(a[i].F >= now - d)
			z ++;
		
		if(z >= x)
			z = 0,
			now ++;
	}
	return 1;
}

int main(){_
	cin >> n >> d >> m;	
	for(int i = 0; i < m ; i ++){
		cin >> a[i].F;
		a[i].S = i + 1;
	}
	
	sort(a, a + m);
	
	int l = 1, r = m;
	while(l < r){
		int mid = (l + r) / 2; 
		if(check(mid))
			r = mid;
		else
			l = mid + 1;
	}
	
	cout << r << '\n';
	int now = 1;
	int z = 0;
	for(int i = 0; i < m ; i ++){
        if(a[i].F > now){
            for (int j = now ; j < a[i].F; j ++)
                cout << 0 << '\n';
                
            n = a[i].F;
            z = 1;
        }
        
        else if (a[i].F >= now - d){
            cout << a[i].S << " ";
            z ++;
        }
        
        if(z >= r){
            cout << 0 << '\n';
            z = 0;
            now ++;
        }
    }
    
    for (int i = now ; i <= n ; i ++)
        cout << 0 << '\n';
}

• Subtask 1: 25 / 100