Submission #446573

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
446573	2021-07-22T13:13:13 Z	ArianKheirandish	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	313 ms	13676 KB

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;
vector < pair<int, int> > a;

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;	
	a.resize(m);
	for(int i = 0; i < m ; i ++){
		cin >> a[i].F;
		a[i].S = i + 1;
	}
	
	sort(all(a));
	
	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';
                
            now = 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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	1604 KB	Output is correct
2	Correct	25 ms	1620 KB	Output is correct
3	Correct	24 ms	1692 KB	Output is correct
4	Correct	24 ms	1652 KB	Output is correct
5	Correct	24 ms	1612 KB	Output is correct
6	Correct	24 ms	1612 KB	Output is correct
7	Correct	26 ms	1620 KB	Output is correct
8	Correct	24 ms	1708 KB	Output is correct
9	Correct	41 ms	1864 KB	Output is correct
10	Correct	40 ms	1868 KB	Output is correct
11	Correct	32 ms	1668 KB	Output is correct
12	Correct	66 ms	3144 KB	Output is correct
13	Correct	102 ms	4548 KB	Output is correct
14	Correct	136 ms	6140 KB	Output is correct
15	Correct	165 ms	7564 KB	Output is correct
16	Correct	204 ms	9104 KB	Output is correct
17	Correct	243 ms	10564 KB	Output is correct
18	Correct	269 ms	12100 KB	Output is correct
19	Correct	313 ms	13676 KB	Output is correct
20	Correct	242 ms	10832 KB	Output is correct