oj.uz

Submission #763183

# Submission time Handle Problem Language Result Execution time Memory
763183 2023-06-22T06:08:15 Z KN200711 Job Scheduling (CEOI12_jobs) C++14
0 / 100
 47 ms 65536 KB 
# include <bits/stdc++.h>
using namespace std;

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

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

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 65536 KB Execution killed with signal 9
2 Runtime error 30 ms 65536 KB Execution killed with signal 9
3 Runtime error 28 ms 65536 KB Execution killed with signal 9
4 Runtime error 29 ms 65536 KB Execution killed with signal 9
5 Runtime error 28 ms 65536 KB Execution killed with signal 9
6 Runtime error 29 ms 65536 KB Execution killed with signal 9
7 Runtime error 30 ms 65536 KB Execution killed with signal 9
8 Runtime error 25 ms 65536 KB Execution killed with signal 9
9 Runtime error 29 ms 65536 KB Execution killed with signal 9
10 Runtime error 30 ms 65536 KB Execution killed with signal 9
11 Runtime error 30 ms 65536 KB Execution killed with signal 9
12 Runtime error 30 ms 65536 KB Execution killed with signal 9
13 Runtime error 30 ms 65536 KB Execution killed with signal 9
14 Runtime error 47 ms 65536 KB Execution killed with signal 9
15 Runtime error 30 ms 65536 KB Execution killed with signal 9
16 Runtime error 28 ms 65536 KB Execution killed with signal 9
17 Runtime error 35 ms 65536 KB Execution killed with signal 9
18 Runtime error 29 ms 65536 KB Execution killed with signal 9
19 Runtime error 29 ms 65536 KB Execution killed with signal 9
20 Runtime error 35 ms 65536 KB Execution killed with signal 9