Submission #1069220

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1069220	2024-08-21T17:41:25 Z	weihong_o	Job Scheduling (CEOI12_jobs)	C++17	65 / 100	249 ms	32108 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=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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	4436 KB	Output is correct
2	Correct	24 ms	4180 KB	Output is correct
3	Correct	25 ms	4268 KB	Output is correct
4	Correct	29 ms	4200 KB	Output is correct
5	Correct	23 ms	4180 KB	Output is correct
6	Correct	24 ms	4180 KB	Output is correct
7	Correct	24 ms	4448 KB	Output is correct
8	Correct	29 ms	4188 KB	Output is correct
9	Correct	43 ms	8072 KB	Output is correct
10	Correct	41 ms	7984 KB	Output is correct
11	Correct	28 ms	3164 KB	Output is correct
12	Runtime error	42 ms	8016 KB	Execution killed with signal 11
13	Runtime error	74 ms	13316 KB	Execution killed with signal 11
14	Runtime error	107 ms	17824 KB	Execution killed with signal 11
15	Runtime error	103 ms	20308 KB	Execution killed with signal 11
16	Runtime error	144 ms	25644 KB	Execution killed with signal 11
17	Runtime error	187 ms	32104 KB	Execution killed with signal 11
18	Correct	223 ms	23620 KB	Output is correct
19	Correct	249 ms	30504 KB	Output is correct
20	Runtime error	188 ms	32108 KB	Execution killed with signal 11