oj.uz

Submission #239335

# Submission time Handle Problem Language Result Execution time Memory
239335 2020-06-15T12:04:18 Z dCoding Job Scheduling (CEOI12_jobs) C++14
65 / 100
 403 ms 41456 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;
	assert(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 47 ms 26084 KB Output is correct
2 Correct 49 ms 26060 KB Output is correct
3 Correct 48 ms 26060 KB Output is correct
4 Correct 51 ms 26060 KB Output is correct
5 Correct 51 ms 25960 KB Output is correct
6 Correct 48 ms 25988 KB Output is correct
7 Correct 50 ms 25940 KB Output is correct
8 Correct 49 ms 25940 KB Output is correct
9 Correct 59 ms 25976 KB Output is correct
10 Correct 61 ms 26108 KB Output is correct
11 Correct 56 ms 25676 KB Output is correct
12 Correct 99 ms 27988 KB Output is correct
13 Correct 138 ms 30200 KB Output is correct
14 Runtime error 185 ms 33140 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
15 Runtime error 219 ms 34040 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
16 Runtime error 277 ms 36856 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
17 Runtime error 307 ms 39672 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
18 Runtime error 363 ms 39928 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
19 Runtime error 403 ms 41456 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
20 Runtime error 322 ms 39800 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)