Submission #104891

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
104891	2019-04-09T13:25:48 Z	groeneprof	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	595 ms	20936 KB

jobs

#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;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	72 ms	4216 KB	Output is correct
2	Correct	78 ms	4244 KB	Output is correct
3	Correct	69 ms	4252 KB	Output is correct
4	Correct	92 ms	4200 KB	Output is correct
5	Correct	84 ms	4212 KB	Output is correct
6	Correct	83 ms	4156 KB	Output is correct
7	Correct	81 ms	4340 KB	Output is correct
8	Correct	72 ms	4216 KB	Output is correct
9	Correct	211 ms	3100 KB	Output is correct
10	Correct	190 ms	3072 KB	Output is correct
11	Correct	54 ms	2552 KB	Output is correct
12	Correct	116 ms	5080 KB	Output is correct
13	Correct	196 ms	7036 KB	Output is correct
14	Correct	197 ms	10064 KB	Output is correct
15	Correct	204 ms	11512 KB	Output is correct
16	Correct	327 ms	13816 KB	Output is correct
17	Correct	402 ms	16172 KB	Output is correct
18	Correct	374 ms	18688 KB	Output is correct
19	Correct	595 ms	20936 KB	Output is correct
20	Correct	349 ms	16120 KB	Output is correct