Submission #645486

#	Time	Username	Problem	Language	Result	Execution time	Memory
645486		kalash04	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	243 ms	21964 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define int long long int

bool check(vector<pair<int, int>>& a, int machines, int delay, int n) {
	int left = machines;
	int i = 0;
	for(int day = 1; day <= n; day++) {
		left = machines;
		while(i < a.size() and a[i].first <= day) {
			if(left > 0) {
				if(a[i].first + delay < day) return false;
				left--;
				i++;
			} else {
				break;
			}
		}
	}
	return (i == a.size());
}

void getday(vector<pair<int, int>>& a, int machines, int delay, int n) {
	int left = machines;
	int i = 0;
	for(int day = 1; day <= n; day++) {
		left = machines;
		while(i < a.size() and a[i].first <= day) {
			if(left > 0) {
				cout << a[i].second << " ";
				left--;
				i++;
			} else {
				break;
			}
		}
		cout << "0\n";
	}
}

void solve() {
	int n, d, m;
	cin >> n >> d >> m;
	vector<pair<int, int>> a(m);
	for(int i = 0; i < m; i++) {
		cin >> a[i].first;
		a[i].second = i + 1;
	}
	sort(a.begin(), a.end());
	int l = 0, r = m;
	while(l < r) {
		int mid = l + (r - l) / 2;
		bool flag = check(a, mid, d, n);
		if(flag) {
			r = mid;
		} else {
			l = mid + 1;
		}
	}
	cout << l << "\n";
	getday(a, l,d, n);
}
 
int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
  cout.tie(NULL);
	solve();
}

Compilation message (stderr)

jobs.cpp: In function 'bool check(std::vector<std::pair<long long int, long long int> >&, long long int, long long int, long long int)':
jobs.cpp:12:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |   while(i < a.size() and a[i].first <= day) {
      |         ~~^~~~~~~~~~
jobs.cpp:22:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  return (i == a.size());
      |          ~~^~~~~~~~~~~
jobs.cpp: In function 'void getday(std::vector<std::pair<long long int, long long int> >&, long long int, long long int, long long int)':
jobs.cpp:30:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   while(i < a.size() and a[i].first <= day) {
      |         ~~^~~~~~~~~~

• Subtask 1: 100 / 100