Submission #734023

#TimeUsernameProblemLanguageResultExecution timeMemory
734023AbodeKuJob Scheduling (CEOI12_jobs)C++17
100 / 100
263 ms20820 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...