oj.uz

Submission #763186

# Submission time Handle Problem Language Result Execution time Memory
763186 2023-06-22T06:11:06 Z KN200711 Job Scheduling (CEOI12_jobs) C++14
20 / 100
 255 ms 20408 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
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 5188 KB Output isn't correct
2 Incorrect 23 ms 5168 KB Output isn't correct
3 Incorrect 23 ms 5220 KB Output isn't correct
4 Incorrect 23 ms 5208 KB Output isn't correct
5 Incorrect 23 ms 5244 KB Output isn't correct
6 Incorrect 23 ms 5224 KB Output isn't correct
7 Incorrect 24 ms 5196 KB Output isn't correct
8 Incorrect 28 ms 5188 KB Output isn't correct
9 Incorrect 32 ms 4876 KB Output isn't correct
10 Incorrect 31 ms 4976 KB Output isn't correct
11 Correct 23 ms 4508 KB Output is correct
12 Correct 51 ms 6776 KB Output is correct
13 Incorrect 74 ms 9168 KB Output isn't correct
14 Correct 114 ms 11844 KB Output is correct
15 Incorrect 106 ms 12860 KB Output isn't correct
16 Correct 132 ms 15744 KB Output is correct
17 Incorrect 187 ms 18648 KB Output isn't correct
18 Incorrect 194 ms 18820 KB Output isn't correct
19 Incorrect 255 ms 20408 KB Output isn't correct
20 Incorrect 189 ms 18576 KB Output isn't correct