oj.uz

Submission #239340

# Submission time Handle Problem Language Result Execution time Memory
239340 2020-06-15T12:12:59 Z dCoding Job Scheduling (CEOI12_jobs) C++14
65 / 100
 377 ms 41336 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 = 1e6,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 54 ms 26132 KB Output is correct
2 Correct 53 ms 26140 KB Output is correct
3 Correct 53 ms 26140 KB Output is correct
4 Correct 52 ms 26204 KB Output is correct
5 Correct 54 ms 26172 KB Output is correct
6 Correct 53 ms 26148 KB Output is correct
7 Correct 54 ms 26280 KB Output is correct
8 Correct 53 ms 26208 KB Output is correct
9 Correct 60 ms 25952 KB Output is correct
10 Correct 64 ms 26104 KB Output is correct
11 Correct 58 ms 25720 KB Output is correct
12 Correct 103 ms 27852 KB Output is correct
13 Correct 140 ms 30200 KB Output is correct
14 Runtime error 190 ms 33176 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
15 Runtime error 218 ms 34040 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
16 Runtime error 277 ms 36588 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
17 Runtime error 336 ms 39928 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
18 Runtime error 340 ms 39880 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
19 Runtime error 377 ms 41336 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
20 Runtime error 324 ms 39672 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)