oj.uz

Submission #239320

# Submission time Handle Problem Language Result Execution time Memory
239320 2020-06-15T11:28:28 Z dCoding Job Scheduling (CEOI12_jobs) C++14
5 / 100
 251 ms 13816 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;
	cout << machines << "\n";
	int	jobNumber = 1;
	F0R(i,n) {
		if(jobNumber > m) {
			cout << "0\n";
			continue;
		}
		F0R(j,machines) {
			if(jobNumber > m) {
				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
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 1784 KB Output isn't correct
2 Incorrect 22 ms 1792 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 25 ms 1792 KB Output isn't correct
5 Incorrect 22 ms 1784 KB Output isn't correct
6 Incorrect 22 ms 1792 KB Output isn't correct
7 Runtime error 15 ms 2176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 15 ms 2176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Incorrect 32 ms 1912 KB Output isn't correct
10 Incorrect 32 ms 1912 KB Output isn't correct
11 Runtime error 24 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Correct 58 ms 3192 KB Output is correct
13 Incorrect 85 ms 4728 KB Output isn't correct
14 Runtime error 86 ms 6904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Incorrect 144 ms 7672 KB Output isn't correct
16 Runtime error 130 ms 10104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Incorrect 207 ms 10616 KB Output isn't correct
18 Incorrect 225 ms 12152 KB Unexpected end of file - int32 expected
19 Incorrect 251 ms 13816 KB Output isn't correct
20 Incorrect 207 ms 10660 KB Output isn't correct