oj.uz

Submission #239334

# Submission time Handle Problem Language Result Execution time Memory
239334 2020-06-15T12:02:29 Z dCoding Job Scheduling (CEOI12_jobs) C++14
65 / 100
 397 ms 44792 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;
int n,d,m;
pii a[MAXM];
vi ans[MAXM];

bool valid(int machines) {
	int mIdx = 1;
	queue<pii> q;
	FOR(i,1,n)ans[i].clear();
	FOR(i,1,n) {
		while(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();
}

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;
	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:45: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:64:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid = lo+hi >> 1;
         ~~^~~

Subtask #1
65.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 26300 KB Output is correct
2 Correct 49 ms 26372 KB Output is correct
3 Correct 51 ms 26244 KB Output is correct
4 Correct 52 ms 26244 KB Output is correct
5 Correct 49 ms 26372 KB Output is correct
6 Correct 49 ms 26352 KB Output is correct
7 Correct 52 ms 26268 KB Output is correct
8 Correct 47 ms 26244 KB Output is correct
9 Correct 58 ms 26232 KB Output is correct
10 Correct 59 ms 26360 KB Output is correct
11 Correct 56 ms 26104 KB Output is correct
12 Correct 95 ms 28600 KB Output is correct
13 Correct 141 ms 31480 KB Output is correct
14 Runtime error 178 ms 34480 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
15 Runtime error 221 ms 35960 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
16 Runtime error 217 ms 36216 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
17 Runtime error 327 ms 42932 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
18 Runtime error 343 ms 42872 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
19 Runtime error 397 ms 44792 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
20 Runtime error 324 ms 43000 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)