Submission #640404

#	Time	Username	Problem	Language	Result	Execution time	Memory
640404		AmirH	Job Scheduling (CEOI12_jobs)	C++14	10 / 100	1095 ms	9184 KiB

jobs

#include<bits/stdc++.h>


using namespace std;
typedef long long int ll;


#define pb push_back
#define faster ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)


const int MAX_N=2e5+25;

int n, d, m;
vector<pair<int, int>> v;

void find(int x) {
	int p = -1;
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < x; j++) {
			p++;
			if(p < v.size()) {
				if(v[p].first > i)
					p--;
				else 
					cout << v[p].second << " ";
			}
		}
		cout << 0 << '\n';
	}
}

bool check(int x) {
	int p = -1;
	bool ok = true;
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < x; j++) {
			p++;
			if(p < v.size()) {
				if(v[p].first > i)
					p--;
				else if(i - v[p].first >= d)
					ok = false;
			}
		}
	}
	return ok;
}

int bs() {
	int l = 0, r = 1e6 + 1;
	while(r - l > 1) {
		int mid = (l + r) / 2;
		if(check(mid))
			r = mid;
		else
			l = mid;
	}
	return r;
}

void input() {
	cin >> n >> d >> m;
	for(int i = 1; i <= m; i++) {
		int x; cin >> x;
		v.pb({x, i});
	}
	sort(v.begin(), v.end());
}

int main() {
	faster;
	input();
	int res = bs();
	cout << res << '\n';
	find(res);
}

Compilation message (stderr)

jobs.cpp: In function 'void find(int)':
jobs.cpp:22:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |    if(p < v.size()) {
      |       ~~^~~~~~~~~~
jobs.cpp: In function 'bool check(int)':
jobs.cpp:39:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    if(p < v.size()) {
      |       ~~^~~~~~~~~~

• Subtask 1: 10 / 100