oj.uz

Submission #763188

# Submission time Handle Problem Language Result Execution time Memory
763188 2023-06-22T06:12:59 Z KN200711 Job Scheduling (CEOI12_jobs) C++14
100 / 100
 215 ms 17072 KB 
# 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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5112 KB Output is correct
2 Correct 23 ms 4936 KB Output is correct
3 Correct 23 ms 4940 KB Output is correct
4 Correct 24 ms 4880 KB Output is correct
5 Correct 23 ms 4868 KB Output is correct
6 Correct 23 ms 4876 KB Output is correct
7 Correct 23 ms 4976 KB Output is correct
8 Correct 23 ms 4952 KB Output is correct
9 Correct 31 ms 4564 KB Output is correct
10 Correct 32 ms 4596 KB Output is correct
11 Correct 23 ms 4172 KB Output is correct
12 Correct 49 ms 6032 KB Output is correct
13 Correct 69 ms 8032 KB Output is correct
14 Correct 113 ms 9944 KB Output is correct
15 Correct 135 ms 11024 KB Output is correct
16 Correct 133 ms 13004 KB Output is correct
17 Correct 160 ms 15280 KB Output is correct
18 Correct 189 ms 15928 KB Output is correct
19 Correct 215 ms 17072 KB Output is correct
20 Correct 177 ms 15272 KB Output is correct