oj.uz

Submission #239347

# Submission time Handle Problem Language Result Execution time Memory
239347 2020-06-15T12:35:21 Z dCoding Job Scheduling (CEOI12_jobs) C++14
100 / 100
 395 ms 20216 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <unordered_map>

#define ll long long int
#define F0R(i,n) for(auto i = 0; i < (n); i++)
#define FOR(i,a,b) for(auto i = (a); i <= (b); i++)
#define ROF(i,a,b) for(auto i = (a); i >= (b); i--)
#define pii pair<int,int> 
#define pll pair<ll,ll>
#define vv vector
#define F first
#define S second
#define pb push_back
#define vi vector<int>

using namespace std;

const int MAXM = 1e6+5;
const int MAXN = 1e5+5;
int n,d,m;
pii a[MAXM];
vi ans[MAXN];

bool valid(int machines) {
	int mIdx = 1;
	queue<pii> q;
	FOR(i,1,n)ans[i].clear();
	FOR(i,1,n) {
		while(mIdx <= m && a[mIdx].F <= i) {
			q.push(a[mIdx]);
			mIdx++;
		}
		while(!q.empty() && ans[i].size() < machines) {
			if(q.front().F+d < i)return false;
			ans[i].pb(q.front().S);
			q.pop();
		}
	}
	return (q.empty() && mIdx > m);
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> d >> m;
	FOR(i,1,m) cin >> a[i].F;
	FOR(i,1,m)a[i].S = i;
	sort(a+1,a+m+1);
	int lo = 1,hi = m,mid;
	while(lo < hi) {
		mid = lo+hi >> 1;
		if(valid(mid)) {
			hi = mid;
		} else {
			lo = mid+1;
		}
	}
	assert(lo == hi);
	int machines = lo;
	valid(machines);
	cout << machines << "\n";
	FOR(i,1,n) {
		for(auto j:ans[i]) cout << j << " ";
		cout << "0\n";
	}
}

Compilation message

jobs.cpp: In function 'bool valid(int)':
jobs.cpp:46:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(!q.empty() && ans[i].size() < machines) {
                       ~~~~~~~~~~~~~~^~~~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:65:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid = lo+hi >> 1;
         ~~^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 4820 KB Output is correct
2 Correct 38 ms 4820 KB Output is correct
3 Correct 37 ms 4940 KB Output is correct
4 Correct 44 ms 4820 KB Output is correct
5 Correct 37 ms 4920 KB Output is correct
6 Correct 38 ms 4908 KB Output is correct
7 Correct 36 ms 4852 KB Output is correct
8 Correct 42 ms 4924 KB Output is correct
9 Correct 47 ms 4856 KB Output is correct
10 Correct 48 ms 4988 KB Output is correct
11 Correct 45 ms 4600 KB Output is correct
12 Correct 90 ms 6840 KB Output is correct
13 Correct 126 ms 9080 KB Output is correct
14 Correct 174 ms 12032 KB Output is correct
15 Correct 208 ms 12920 KB Output is correct
16 Correct 255 ms 15736 KB Output is correct
17 Correct 309 ms 18680 KB Output is correct
18 Correct 339 ms 18680 KB Output is correct
19 Correct 395 ms 20216 KB Output is correct
20 Correct 314 ms 18552 KB Output is correct