Submission #763188

#	Time	Username	Problem	Language	Result	Execution time	Memory
763188		KN200711	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	215 ms	17072 KiB

jobs

# include <bits/stdc++.h>
using namespace std;

int arr[1000001];
vector<int> pos[100001];
int N, D, M;

bool cek(int a) {
	deque<pair<int, int> > d;
	d.clear();
	for(int c=1;c<=N;c++) {
		d.push_front(make_pair(pos[c].size(), c));
		int V = a;
		while(d.size() && d.back().first <= V) {
		//	if(a == 2) cout<<"V : "<<V<<endl;
			V -= d.back().first;
			d.pop_back();
		}
		if(d.size() && d.back().first > V) {
			d.back().first -= V;
		} 
		
	//	if(a == 2) cout<<c<<" "<<d.size()<<" "<<d.back().second<<endl;
		if(d.size() > 0 && d.back().second + D <= c) return 0;
	}
	return 1;
}

int main() {
	
	scanf("%d %d %d", &N, &D, &M);
	
	for(int i=0;i<M;i++) {
		scanf("%d", &arr[i]);
		pos[arr[i]].push_back(i);
	}
	
	int lf = 0, rg = 1e6, ans = -1;
//	cout<<cek(2)<<endl;
	while(lf <= rg) {
		int mid = (lf + rg) / 2;
		if(cek(mid)) {
			ans = mid;
			rg = mid - 1;
		} else lf = mid + 1;
	}
	
	printf("%d\n", ans);
	priority_queue< pair<int, int> > PQ;
	for(int i=1;i<=N;i++) {
	//	cout<<i<<endl;
		for(int k=0;k<pos[i].size();k++) {
			PQ.push(make_pair(-i, pos[i][k]));
			
		}
		int V = ans;
		while(PQ.size() && V) {
			printf("%d ", PQ.top().second + 1);
			PQ.pop();
			V--;
		}
		printf("0\n");
	}
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int k=0;k<pos[i].size();k++) {
      |               ~^~~~~~~~~~~~~~
jobs.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  scanf("%d %d %d", &N, &D, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   scanf("%d", &arr[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 100 / 100