Submission #77251

#	Time	Username	Problem	Language	Result	Execution time	Memory
77251		Vardanyan	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	359 ms	21128 KiB

jobs

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1000 * 100 + 7;
int day[N];
vector<int> g[N];
vector<int> as[N];
int main(){
	int n, d, m;
	scanf("%d%d%d", &n, &d, &m);
	for (int i = 1; i <= m; i++){
		int p;
		scanf("%d", &p);
		day[p]++;
		g[p].push_back(i);
	}
	int l = 1;
	int r = m;
	int ans = m;
	
	queue<int> q;
	while (l <= r){
		while (!q.empty()) q.pop();
		int mid = (l + r) / 2;
		for (int i = 1; i <= n; i++){
			int x = day[i];
			while (x--) q.push(i);
			bool f = true;
			int num = mid;
			while (!q.empty()){
				int v = q.front();
				if (i > v + d){
					f = false;
					break;
				}
				if (num > 0){
					q.pop();
					num--;
				}
				else break;
			}
		}
		if (q.empty()) {
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	int mid = ans;
	while (!q.empty()) q.pop();
	
	for (int i = 1; i <= n; i++){
		int x = day[i];
		while (x--) q.push(i);
		bool f = true;
		int num = mid;
		while (!q.empty()){
			int v = q.front();
			if (i > v + d){
				f = false;
				break;
			}
			if (num > 0){
				q.pop();
				num--;
				as[i].push_back(v);
			}
			else break;
		}
	}
	cout << ans << endl;
	for (int i = 1; i <= n; i++){
		for (int j = 0; j < as[i].size(); j++){
			int l = as[i][j];
			int e = g[l][g[l].size() - 1];
			printf("%d ", e);
			g[l].pop_back();
		}
		printf("%d\n", 0);
	}
	return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:30:9: warning: variable 'f' set but not used [-Wunused-but-set-variable]
    bool f = true;
         ^
jobs.cpp:57:8: warning: variable 'f' set but not used [-Wunused-but-set-variable]
   bool f = true;
        ^
jobs.cpp:75:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < as[i].size(); j++){
                   ~~^~~~~~~~~~~~~~
jobs.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &d, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &p);
   ~~~~~^~~~~~~~~~

• Subtask 1: 100 / 100