Submission #981539

#	Time	Username	Problem	Language	Result	Execution time	Memory
981539		SmuggingSpun	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	103 ms	13648 KiB

jobs

#include<bits/stdc++.h>
#define taskname "jobs"
using namespace std;
const int lim = 1e5 + 5;
vector<int>p[lim];
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	int n, d, m;
	cin >> n >> d >> m;
	for(int i = 0; i < m; ){
		int x;
		cin >> x;
		p[x].emplace_back(++i);
	}
	int low = 1, high = m, ans;
	while(low <= high){
		int mid = (low + high) >> 1;
		deque<pair<int, int>>D;
		for(int i = 1; i <= n; i++){
			int current = mid;
			if(!p[i].empty() > 0){
				D.emplace_back(i, p[i].size());
			}
			if(!D.empty() && D.front().first + d < i){
				break;
			}
			while(!D.empty()){
				auto [x, y] = D.front();
				D.pop_front();
				if(current >= y){
					current -= y;
				}
				else{
					D.emplace_front(x, y - current);
					break;
				}
			}
		}
		if(!D.empty()){
			low = mid + 1;
		}
		else{
			high = (ans = mid) - 1;
		}
	}
	cout << ans << "\n";
	queue<int>q;
	for(int i = 1; i <= n; i++){
		for(int& x : p[i]){
			q.push(x);
		}
		for(int _ = 0; _ < ans && !q.empty(); _++, q.pop()){
			cout << q.front() << " ";
		}
		cout << "0\n";
	}
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:31:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     auto [x, y] = D.front();
      |          ^
jobs.cpp:9:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |   freopen(taskname".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:55:26: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |   for(int _ = 0; _ < ans && !q.empty(); _++, q.pop()){
      |                  ~~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 100 / 100