oj.uz

Submission #132239

# Submission time Handle Problem Language Result Execution time Memory
132239 2019-07-18T14:48:26 Z Atalasion Job Scheduling (CEOI12_jobs) C++14
60 / 100
 654 ms 23356 KB 
#include <bits/stdc++.h>

#define pb push_back
#define all(x) x.begin(), x.end()
#define F first 
#define S second

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;
typedef string str;

const ll MOD = 1e9 + 7;
const ll N = 1e6 + 10;
const ll INF = 1e18;

ll n, d, m;

pll a[N];

bool isval(ll x){
	queue <pll> q;
	ll pnt = 1;
	//cout << x << '\n';
	for (int i = 1; i <= n; i++){
		if (pnt != m + 1){
			while ((pnt != m + 1) && (a[pnt].F == i)) q.push(a[pnt]), pnt ++;
		}
		//cout << i << ' ' << pnt << ' ' << q.size() << ' ' << x << ' ';
		for (int j = 0; j < x; j++){
		    if (q.size() == 0) break;
		    q.pop();
		}
		//cout << q.size() << '\n';
		if (q.size() != 0){
			if (q.front().F + d < i + 1){
				return 0;
			}
		}
	}
	if (q.size()) return 0;
	return 1;
}


int main(){
	cin >> n >> d >> m;
	for (int i = 1; i <= m; i++){
		ll v;
		cin >> v;
		a[i] = {v, i};
	}
	sort(a + 1, a + m + 1);
	ll l = 0, r = n;
	while (r - l > 1){
		ll mid = (l + r) / 2;
		//cout << l << ' ' << r << '\n';
		if (isval(mid)) r = mid;
		else l = mid;
	}
	cout << r << '\n';
	ll x = r;
	queue <pll> q;
	ll pnt = 1;
	for (int i = 1; i <= n; i++){
		if (pnt != m + 1){
			while ((pnt != m + 1) && (a[pnt].F == i)) q.push(a[pnt]), pnt ++;
		}
		//cout << i << ' ' << pnt << ' ' << q.size() << ' ' << x << ' ';
		for (int j = 0; j < x; j++){
		    if (q.size() == 0) break;
			cout << q.front().S << ' ';
		    q.pop();
		}
		cout << 0 << '\n';
		//cout << q.size() << '\n';
		if (q.size() != 0){
			if (q.front().F + d < i + 1){
				return 0;
			}
		}
	}
	
	
	
	
	
	
	return 0;
}
	/*8 2 12
	1 2 4 2 1 3 5 6 2 3 6 4*/

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 3672 KB Output isn't correct
2 Incorrect 59 ms 3672 KB Output isn't correct
3 Incorrect 57 ms 3624 KB Output isn't correct
4 Incorrect 61 ms 3672 KB Output isn't correct
5 Incorrect 61 ms 3672 KB Output isn't correct
6 Incorrect 59 ms 3608 KB Output isn't correct
7 Incorrect 60 ms 3928 KB Output isn't correct
8 Incorrect 59 ms 3900 KB Output isn't correct
9 Correct 79 ms 3016 KB Output is correct
10 Correct 81 ms 3108 KB Output is correct
11 Correct 67 ms 2892 KB Output is correct
12 Correct 141 ms 5916 KB Output is correct
13 Correct 198 ms 7180 KB Output is correct
14 Correct 321 ms 10768 KB Output is correct
15 Correct 342 ms 13584 KB Output is correct
16 Correct 460 ms 13944 KB Output is correct
17 Correct 537 ms 16376 KB Output is correct
18 Correct 564 ms 18992 KB Output is correct
19 Correct 654 ms 23356 KB Output is correct
20 Correct 549 ms 18680 KB Output is correct