oj.uz

Submission #734023

# Submission time Handle Problem Language Result Execution time Memory
734023 2023-05-01T14:00:23 Z AbodeKu Job Scheduling (CEOI12_jobs) C++17
100 / 100
 263 ms 20820 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<pair<ll,ll>> vpi;
typedef vector<vector<ll>> vvi;
const double EBS = 1e-9;

#define testCase ll t; cin >> t; while (t--)
#define fast  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(f, s, i) for (ll i = f; i < s; i++)
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
#define calunique(v)  disance(v.begin(),unique(v.begin(),v.end()));
#define popcount(i) __builtin_popcount(i)
#define el cout << "\n"
#define pb push_back
#define pf push_front
#define no cout << "NO\n"
#define yes cout << "YES\n"
#define all(v) v.begin(), v.end()
#define PII pair<ll,ll>
#define INF (ll)1e9
#define INFLL (ll)1e18
#define debug cout << "___________________________________" << endl
#define int ll

int n , d , k ; 
vpi a ;

bool check(int num){
	int idx = 0 ; 
	rep(1 , n + 1 , i){
		int cnt = 0 ; 
		while(i >= a[idx].first && idx < k && cnt < num){
			if (i > a[idx].first + d ) return 0 ; 
			idx++;
			cnt++;
			
		}
		
	}
	return 1 ;
}

int32_t main(){
	fast ;
	cin >> n >> d >> k ; 
	a = vpi(k);
	rep(0 , k , i ) cin >> a[i].first , a[i].second = i+1 ;
	sort(all(a));
	int l = 0 , r = k ; 
	int ans = 0 ; 
	while(l  < r ){
		int mid = (l + r) / 2 ; 
		if (check(mid)){
			ans = mid ; 
			r = mid ;
		}else{
			l = mid + 1;
		}
	}
	
	cout << ans << endl ;
	int idx = 0 ; 
	rep(0 , n , i){
		int cnt = 0 ;
		while(cnt < ans && idx < k ) cout << a[idx++].second << " " ,  cnt++ ;
		cout << "0\n";
	}
	
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2436 KB Output is correct
2 Correct 17 ms 2504 KB Output is correct
3 Correct 16 ms 2516 KB Output is correct
4 Correct 18 ms 2388 KB Output is correct
5 Correct 16 ms 2388 KB Output is correct
6 Correct 18 ms 2516 KB Output is correct
7 Correct 18 ms 2408 KB Output is correct
8 Correct 17 ms 2388 KB Output is correct
9 Correct 30 ms 2668 KB Output is correct
10 Correct 28 ms 2636 KB Output is correct
11 Correct 27 ms 2400 KB Output is correct
12 Correct 56 ms 4732 KB Output is correct
13 Correct 75 ms 6988 KB Output is correct
14 Correct 105 ms 9264 KB Output is correct
15 Correct 137 ms 11468 KB Output is correct
16 Correct 156 ms 13800 KB Output is correct
17 Correct 198 ms 16004 KB Output is correct
18 Correct 211 ms 18340 KB Output is correct
19 Correct 263 ms 20820 KB Output is correct
20 Correct 216 ms 16076 KB Output is correct