Submission #1069220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069220		weihong_o	Job Scheduling (CEOI12_jobs)	C++17	65 / 100	249 ms	32108 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-D+1);

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

		v=v&&k==M;

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

	cout<<ans<<'\n';
	rep(i,1,N+1) {
		if(i<ans_v.size()) 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();
}

Compilation message (stderr)

jobs.cpp: In function 'void solve()':
jobs.cpp:54:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   if(i<ans_v.size()) for(auto j: ans_v[i]) cout<<j<<' ';
      |      ~^~~~~~~~~~~~~

• Subtask 1: 65 / 100