Submission #1069223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069223		weihong_o	Job Scheduling (CEOI12_jobs)	C++17	85 / 100	249 ms	26916 KiB

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=1000000;
	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) {
			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: 85 / 100