oj.uz

답안 #1069220

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1069220 2024-08-21T17:41:25 Z weihong_o Job Scheduling (CEOI12_jobs) C++17
65 / 100
 249 ms 32108 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-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

# 결과 실행 시간 메모리 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