oj.uz

답안 #104891

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
104891 2019-04-09T13:25:48 Z groeneprof Job Scheduling (CEOI12_jobs) C++14
100 / 100
 595 ms 20936 KB 
#include <bits/stdc++.h>
#define int long long
#define P(x) do {if(debug) cout << x << endl;} while(false)
#define H(x) P(#x << ": " << x)
#define FR(i, a, b) for(int i = (a); i < (b); ++i)
#define F(i, n) FR(i, 0, n)
#define DR(i, a, b) for(int i = (b); i --> (a);)
#define D(i, n) DR(i, 0, n)
#define S(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()
#define MI(x, a) (x) = min(x, a)
#define MA(x, a) (x) = max(x, a)
#define V vector
#define pb push_back
#define mp make_pair
using namespace std;
const bool debug = 1;
int N,M,D;
vector<pair<int, int> > jobs;

bool possible(int A, bool bol){
	queue<pair<int,int> > q;
	int i = 0;
	F(d,N){
		if(!q.empty()&&q.front().first<d){
			return false;
		}
		while(i<M&&jobs[i].first==d){
			q.push({d+D,jobs[i].second});
			i++;
		}
		for(int j = 0; j < A && !q.empty(); j++){
			if(bol){
				cout<<q.front().second+1<<" ";
			}
			q.pop();
		}
		if(bol){
			cout<<0<<endl;
		}
	}
	return true;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>N>>D>>M;
	jobs.resize(M);
	F(i, M){
		cin>>jobs[i].first;
		jobs[i].second=i;
		jobs[i].first--;
	}
	sort(jobs.begin(), jobs.end());
	int res = 0;
	for(int bs = 1<<23; bs>=1; bs>>=1){
		if(!possible(res|bs, false)){
			res|=bs;
		}
	}
	res++;
	cout<<res<<endl;
	possible(res, true);
	return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 4216 KB Output is correct
2 Correct 78 ms 4244 KB Output is correct
3 Correct 69 ms 4252 KB Output is correct
4 Correct 92 ms 4200 KB Output is correct
5 Correct 84 ms 4212 KB Output is correct
6 Correct 83 ms 4156 KB Output is correct
7 Correct 81 ms 4340 KB Output is correct
8 Correct 72 ms 4216 KB Output is correct
9 Correct 211 ms 3100 KB Output is correct
10 Correct 190 ms 3072 KB Output is correct
11 Correct 54 ms 2552 KB Output is correct
12 Correct 116 ms 5080 KB Output is correct
13 Correct 196 ms 7036 KB Output is correct
14 Correct 197 ms 10064 KB Output is correct
15 Correct 204 ms 11512 KB Output is correct
16 Correct 327 ms 13816 KB Output is correct
17 Correct 402 ms 16172 KB Output is correct
18 Correct 374 ms 18688 KB Output is correct
19 Correct 595 ms 20936 KB Output is correct
20 Correct 349 ms 16120 KB Output is correct