Submission #1069228

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1069228	2024-08-21T17:47:22 Z	weihong_o	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	276 ms	26924 KB

jobs

#include <bits/extc++.h>
#include <bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)(x).size()
#define LSB(x) (x) & (-x)
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int N,D,M,ans=-1;
vector<vi> ans_v;
vector<pii> reqs;

void solve() {
	cin>>N>>D>>M;
	reqs.resize(M);
	rep(i,0,M) cin>>reqs[i].fi,reqs[i].se=i;
	sort(all(reqs));

	int lb=1,ub=M;
	while(lb<=ub) {
		int mb=(lb+ub)/2;
		queue<int> q;
		vector<vi> curr(N+1);

		bool v=1;
		int k=0;
		rep(i,1,N+1) {
			for(;k<M&&reqs[k].fi==i;++k) q.push(k);
			if(q.size()&&reqs[q.front()].fi+D<i) {
				v=0;
				break;
			}
			for(int j=0;j<mb&&q.size();++j) {
				curr[i].push_back(reqs[q.front()].se+1);
				q.pop();
			}
		}

		v = v&(q.empty());

		if(v) ans=mb,ans_v=curr,ub=mb-1;
		else lb=mb+1;
	}

	cout<<ans<<'\n';
	rep(i,1,N+1) {
		for(auto j: ans_v[i]) cout<<j<<' ';
		cout<<"0\n";
	}
}

int main() {
	//freopen("convention2.in", "r", stdin);
	//freopen("convention2.out", "w", stdout);
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	solve();
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	3180 KB	Output is correct
2	Correct	29 ms	3200 KB	Output is correct
3	Correct	40 ms	3172 KB	Output is correct
4	Correct	31 ms	3156 KB	Output is correct
5	Correct	23 ms	3232 KB	Output is correct
6	Correct	25 ms	3184 KB	Output is correct
7	Correct	24 ms	3320 KB	Output is correct
8	Correct	33 ms	3228 KB	Output is correct
9	Correct	38 ms	7724 KB	Output is correct
10	Correct	38 ms	7720 KB	Output is correct
11	Correct	26 ms	2908 KB	Output is correct
12	Correct	58 ms	5204 KB	Output is correct
13	Correct	79 ms	8184 KB	Output is correct
14	Correct	129 ms	11620 KB	Output is correct
15	Correct	133 ms	12624 KB	Output is correct
16	Correct	179 ms	15460 KB	Output is correct
17	Correct	221 ms	19816 KB	Output is correct
18	Correct	235 ms	20584 KB	Output is correct
19	Correct	276 ms	26924 KB	Output is correct
20	Correct	220 ms	20028 KB	Output is correct