Submission #1261525

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261525		mirbek01	Job Scheduling (CEOI12_jobs)	C++20	40 / 100	282 ms	23912 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	int n, d, m;
	cin >> n >> d >> m;
	
	vector <int> vec[n + 1];
	vector <int> a(m + 1);
	for (int i = 1; i <= m; i++) {
		cin >> a[i];
		vec[a[i]].push_back(i);
	}
	
	for (int i = 1; i <= n; i++) {
		reverse(vec[i].begin(), vec[i].end());
	}
	
	int l = 0, r = m;
	while (r - l > 1) {
		int mid = (l + r) >> 1;
		queue <int> dq;
		vector <int> res(m + 1, 2e18);
		for (int i = 1; i <= n; i++) {
			for (auto x : vec[i]) dq.push(x);
			for (int j = 0; j < mid; j++) 
			{
				if (dq.empty()) break;
				res[dq.front()] = i;
				dq.pop();
			}
		}
		
		int flag = 1;
		for (int i = 1; i <= m; i++) {
			if (res[i] - i > m) flag = 0;
		}
		
		if (flag) r = mid;
		else l = mid;
	}
	
	cout << r << endl;
	queue <int> dq;
	for (int i = 1; i <= n; i++) {
		for (auto x : vec[i]) dq.push(x);
		for (int j = 0; j < r; j++) 
		{
			if (dq.empty()) break;
			cout << dq.front() << " ";
			dq.pop();
		}
		cout << 0 << endl;
	}
}
	

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:25:41: warning: overflow in conversion from 'double' to 'std::vector<int>::value_type' {aka 'int'} changes value from '2.0e+18' to '2147483647' [-Woverflow]
   25 |                 vector <int> res(m + 1, 2e18);
      |                                         ^~~~

• Subtask 1: 40 / 100