oj.uz

Submission #239336

# Submission time Handle Problem Language Result Execution time Memory
239336 2020-06-15T12:06:43 Z dCoding Job Scheduling (CEOI12_jobs) C++14
65 / 100
 407 ms 41404 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;
	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 50 ms 25972 KB Output is correct
3 Correct 52 ms 26168 KB Output is correct
4 Correct 52 ms 26076 KB Output is correct
5 Correct 50 ms 25940 KB Output is correct
6 Correct 50 ms 25972 KB Output is correct
7 Correct 52 ms 25940 KB Output is correct
8 Correct 62 ms 26060 KB Output is correct
9 Correct 60 ms 25980 KB Output is correct
10 Correct 64 ms 26104 KB Output is correct
11 Correct 61 ms 25720 KB Output is correct
12 Correct 96 ms 27960 KB Output is correct
13 Correct 140 ms 30200 KB Output is correct
14 Runtime error 194 ms 33148 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
15 Runtime error 221 ms 34076 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
16 Runtime error 268 ms 36860 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
17 Runtime error 330 ms 39748 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
18 Runtime error 356 ms 39800 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
19 Runtime error 407 ms 41404 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
20 Runtime error 335 ms 39672 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)