oj.uz

Submission #239338

# Submission time Handle Problem Language Result Execution time Memory
239338 2020-06-15T12:08:08 Z dCoding Job Scheduling (CEOI12_jobs) C++14
65 / 100
 408 ms 41608 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 48 ms 26060 KB Output is correct
2 Correct 51 ms 26068 KB Output is correct
3 Correct 53 ms 25948 KB Output is correct
4 Correct 48 ms 25972 KB Output is correct
5 Correct 48 ms 26040 KB Output is correct
6 Correct 53 ms 25972 KB Output is correct
7 Correct 50 ms 25972 KB Output is correct
8 Correct 53 ms 25940 KB Output is correct
9 Correct 63 ms 25976 KB Output is correct
10 Correct 63 ms 26104 KB Output is correct
11 Correct 58 ms 25720 KB Output is correct
12 Correct 96 ms 27960 KB Output is correct
13 Correct 143 ms 30200 KB Output is correct
14 Runtime error 193 ms 33276 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
15 Runtime error 222 ms 34040 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
16 Runtime error 268 ms 36856 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
17 Runtime error 314 ms 39672 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
18 Runtime error 341 ms 39776 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
19 Runtime error 408 ms 41608 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
20 Runtime error 312 ms 39792 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)