oj.uz

Submission #1069223

# Submission time Handle Problem Language Result Execution time Memory
1069223 2024-08-21T17:45:22 Z weihong_o Job Scheduling (CEOI12_jobs) C++17
85 / 100
 249 ms 26916 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3936 KB Output is correct
2 Correct 25 ms 3936 KB Output is correct
3 Correct 26 ms 3932 KB Output is correct
4 Correct 24 ms 3932 KB Output is correct
5 Correct 25 ms 3932 KB Output is correct
6 Correct 25 ms 3936 KB Output is correct
7 Correct 24 ms 3924 KB Output is correct
8 Correct 26 ms 4180 KB Output is correct
9 Correct 46 ms 7720 KB Output is correct
10 Correct 42 ms 7720 KB Output is correct
11 Correct 29 ms 2896 KB Output is correct
12 Incorrect 58 ms 5168 KB Output isn't correct
13 Correct 82 ms 8312 KB Output is correct
14 Incorrect 132 ms 11624 KB Output isn't correct
15 Incorrect 139 ms 12572 KB Output isn't correct
16 Correct 176 ms 15416 KB Output is correct
17 Correct 230 ms 19792 KB Output is correct
18 Correct 215 ms 20552 KB Output is correct
19 Correct 249 ms 26916 KB Output is correct
20 Correct 224 ms 19816 KB Output is correct