oj.uz

Submission #239339

# Submission time Handle Problem Language Result Execution time Memory
239339 2020-06-15T12:09:05 Z dCoding Job Scheduling (CEOI12_jobs) C++14
65 / 100
 394 ms 41388 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(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();
}

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: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 49 ms 25940 KB Output is correct
2 Correct 51 ms 26060 KB Output is correct
3 Correct 50 ms 26188 KB Output is correct
4 Correct 55 ms 25972 KB Output is correct
5 Correct 48 ms 25940 KB Output is correct
6 Correct 51 ms 25940 KB Output is correct
7 Correct 48 ms 25940 KB Output is correct
8 Correct 51 ms 26064 KB Output is correct
9 Correct 65 ms 25976 KB Output is correct
10 Correct 61 ms 26104 KB Output is correct
11 Correct 58 ms 25720 KB Output is correct
12 Correct 104 ms 27960 KB Output is correct
13 Correct 143 ms 30200 KB Output is correct
14 Runtime error 188 ms 33152 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
15 Runtime error 221 ms 34168 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
16 Runtime error 270 ms 36856 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
17 Runtime error 318 ms 39672 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
18 Runtime error 348 ms 39928 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
19 Runtime error 394 ms 41388 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
20 Runtime error 336 ms 39804 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)