oj.uz

Submission #239319

# Submission time Handle Problem Language Result Execution time Memory
239319 2020-06-15T11:27:01 Z dCoding Job Scheduling (CEOI12_jobs) C++14
10 / 100
 203 ms 11768 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];

bool valid(int machines) {
	FOR(i,1,n) {
		int maxjob = machines*i;
		maxjob = min(maxjob,m);
		int minjob = machines*(i-1)+1;
		if(i-a[minjob].F > d) {
			return false;
		}
		if(maxjob == m)break;
	}
	return true;
}

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-1;
		} else {
			lo = mid+1;
		}
	}
	assert(lo == hi);
	int machines = lo;
	if(m%machines != 0) {
		int num = m/machines;
		m = machines/num;
	}
	if(!valid(m))++m;
	cout << machines << "\n";
	int	jobNumber = 1;
	F0R(i,n) {
		if(jobNumber > m) {
			cout << "0\n";
			continue;
		}
		F0R(j,machines) {
			if(jobNumber > m) {
				cout << "0\n";
				// goto nextDay;
			} else {
				cout << a[jobNumber++].S << " ";
			}
		}
	
		cout << "0\n";
		// nextDay:;
	}
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:58:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid = lo+hi >> 1;
         ~~^~~

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 1408 KB Output isn't correct
2 Incorrect 13 ms 1408 KB Output isn't correct
3 Runtime error 15 ms 2432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 13 ms 1536 KB Output isn't correct
5 Incorrect 13 ms 1408 KB Output isn't correct
6 Incorrect 15 ms 1408 KB Output isn't correct
7 Runtime error 14 ms 2432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 15 ms 2560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Incorrect 24 ms 1536 KB Output isn't correct
10 Incorrect 27 ms 1664 KB Output isn't correct
11 Runtime error 26 ms 2688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Correct 57 ms 3964 KB Output is correct
13 Incorrect 84 ms 5880 KB Output isn't correct
14 Runtime error 87 ms 8056 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Incorrect 141 ms 8904 KB Output isn't correct
16 Runtime error 131 ms 11128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Incorrect 203 ms 11768 KB Output isn't correct
18 Correct 162 ms 7804 KB Output is correct
19 Incorrect 181 ms 8828 KB Output isn't correct
20 Incorrect 203 ms 11768 KB Output isn't correct