oj.uz

Submission #239304

# Submission time Handle Problem Language Result Execution time Memory
239304 2020-06-15T10:16:21 Z dCoding Job Scheduling (CEOI12_jobs) C++14
10 / 100
 206 ms 10620 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);
		if(i-a[maxjob].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;
	}
	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:57: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 13 ms 1152 KB Output isn't correct
2 Incorrect 13 ms 1152 KB Output isn't correct
3 Runtime error 16 ms 2176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 14 ms 1152 KB Output isn't correct
5 Incorrect 14 ms 1152 KB Output isn't correct
6 Incorrect 13 ms 1152 KB Output isn't correct
7 Runtime error 14 ms 2304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 21 ms 2176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Incorrect 24 ms 1280 KB Output isn't correct
10 Incorrect 24 ms 1280 KB Output isn't correct
11 Incorrect 23 ms 1152 KB Output isn't correct
12 Correct 59 ms 3284 KB Output is correct
13 Incorrect 84 ms 4796 KB Output isn't correct
14 Runtime error 85 ms 6904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Incorrect 150 ms 7756 KB Output isn't correct
16 Runtime error 130 ms 9976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Incorrect 203 ms 10620 KB Output isn't correct
18 Correct 154 ms 6648 KB Output is correct
19 Incorrect 183 ms 7544 KB Output isn't correct
20 Incorrect 206 ms 10616 KB Output isn't correct