Submission #104891

#TimeUsernameProblemLanguageResultExecution timeMemory
104891groeneprofJob Scheduling (CEOI12_jobs)C++14
100 / 100
595 ms20936 KiB
#include <bits/stdc++.h>
#define int long long
#define P(x) do {if(debug) cout << x << endl;} while(false)
#define H(x) P(#x << ": " << x)
#define FR(i, a, b) for(int i = (a); i < (b); ++i)
#define F(i, n) FR(i, 0, n)
#define DR(i, a, b) for(int i = (b); i --> (a);)
#define D(i, n) DR(i, 0, n)
#define S(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()
#define MI(x, a) (x) = min(x, a)
#define MA(x, a) (x) = max(x, a)
#define V vector
#define pb push_back
#define mp make_pair
using namespace std;
const bool debug = 1;
int N,M,D;
vector<pair<int, int> > jobs;

bool possible(int A, bool bol){
	queue<pair<int,int> > q;
	int i = 0;
	F(d,N){
		if(!q.empty()&&q.front().first<d){
			return false;
		}
		while(i<M&&jobs[i].first==d){
			q.push({d+D,jobs[i].second});
			i++;
		}
		for(int j = 0; j < A && !q.empty(); j++){
			if(bol){
				cout<<q.front().second+1<<" ";
			}
			q.pop();
		}
		if(bol){
			cout<<0<<endl;
		}
	}
	return true;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>N>>D>>M;
	jobs.resize(M);
	F(i, M){
		cin>>jobs[i].first;
		jobs[i].second=i;
		jobs[i].first--;
	}
	sort(jobs.begin(), jobs.end());
	int res = 0;
	for(int bs = 1<<23; bs>=1; bs>>=1){
		if(!possible(res|bs, false)){
			res|=bs;
		}
	}
	res++;
	cout<<res<<endl;
	possible(res, true);
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...