oj.uz

Submission #239302

# Submission time Handle Problem Language Result Execution time Memory
239302 2020-06-15T10:10:49 Z dCoding Job Scheduling (CEOI12_jobs) C++14
20 / 100
 256 ms 13816 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.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;
		}
	}
	int machines = lo;
	cout << machines << "\n";
	int	jobNumber = 1;
	F0R(i,n) {
		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:56:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid = lo+hi >> 1;
         ~~^~~

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 1784 KB Output isn't correct
2 Incorrect 22 ms 1792 KB Output isn't correct
3 Incorrect 22 ms 1784 KB Output isn't correct
4 Incorrect 21 ms 1792 KB Output isn't correct
5 Incorrect 20 ms 1792 KB Output isn't correct
6 Incorrect 20 ms 1792 KB Output isn't correct
7 Incorrect 20 ms 1792 KB Output isn't correct
8 Incorrect 21 ms 1792 KB Output isn't correct
9 Incorrect 33 ms 1912 KB Output isn't correct
10 Incorrect 32 ms 1912 KB Output isn't correct
11 Incorrect 31 ms 1792 KB Output isn't correct
12 Correct 66 ms 3272 KB Output is correct
13 Incorrect 86 ms 4728 KB Output isn't correct
14 Correct 127 ms 6264 KB Output is correct
15 Incorrect 139 ms 7672 KB Output isn't correct
16 Correct 173 ms 9208 KB Output is correct
17 Incorrect 206 ms 10820 KB Output isn't correct
18 Correct 227 ms 12152 KB Output is correct
19 Incorrect 256 ms 13816 KB Output isn't correct
20 Incorrect 213 ms 10720 KB Output isn't correct