oj.uz

Submission #640406

# Submission time Handle Problem Language Result Execution time Memory
640406 2022-09-14T14:56:48 Z AmirH Job Scheduling (CEOI12_jobs) C++14
30 / 100
 901 ms 13852 KB 
#include<bits/stdc++.h>


using namespace std;
typedef long long int ll;


#define pb push_back
#define faster ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)


const int MAX_N=2e5+25;

int n, d, m;
vector<pair<int, int>> v;

void find(int x) {
	int p = -1;
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < x; j++) {
			p++;
			if(p >= v.size())
				break;
			if(p < v.size()) {
				if(v[p].first > i)
					p--;
				else 
					cout << v[p].second << " ";
			}
		}
		cout << 0 << '\n';
	}
}

bool check(int x) {
	int p = -1;
	bool ok = true;
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < x; j++) {
			p++;
			if(p >= v.size())
				break;
			if(p < v.size()) {
				if(v[p].first > i)
					p--;
				else if(i - v[p].first >= d)
					ok = false;
			}
		}
	}
	return ok;
}

int bs() {
	int l = 0, r = 1e5 + 1;
	while(r - l > 1) {
		int mid = (l + r) / 2;
		if(check(mid))
			r = mid;
		else
			l = mid;
	}
	return r;
}

void input() {
	cin >> n >> d >> m;
	for(int i = 1; i <= m; i++) {
		int x; cin >> x;
		v.pb({x, i});
	}
	sort(v.begin(), v.end());
}

int main() {
	faster;
	input();
	int res = bs();
	cout << res << '\n';
	find(res);
}

Compilation message

jobs.cpp: In function 'void find(int)':
jobs.cpp:22:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |    if(p >= v.size())
      |       ~~^~~~~~~~~~~
jobs.cpp:24:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |    if(p < v.size()) {
      |       ~~^~~~~~~~~~
jobs.cpp: In function 'bool check(int)':
jobs.cpp:41:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |    if(p >= v.size())
      |       ~~^~~~~~~~~~~
jobs.cpp:43:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    if(p < v.size()) {
      |       ~~^~~~~~~~~~

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 1816 KB Output isn't correct
2 Incorrect 59 ms 1752 KB Output isn't correct
3 Incorrect 56 ms 1752 KB Output isn't correct
4 Incorrect 74 ms 1828 KB Output isn't correct
5 Incorrect 95 ms 1736 KB Output isn't correct
6 Incorrect 99 ms 1752 KB Output isn't correct
7 Incorrect 102 ms 1748 KB Output isn't correct
8 Incorrect 118 ms 1756 KB Output isn't correct
9 Incorrect 39 ms 2000 KB Output isn't correct
10 Incorrect 35 ms 1948 KB Output isn't correct
11 Correct 92 ms 1736 KB Output is correct
12 Incorrect 123 ms 3288 KB Output isn't correct
13 Correct 159 ms 4732 KB Output is correct
14 Incorrect 750 ms 6356 KB Output isn't correct
15 Incorrect 199 ms 7764 KB Output isn't correct
16 Correct 897 ms 9260 KB Output is correct
17 Correct 901 ms 10676 KB Output is correct
18 Correct 300 ms 12420 KB Output is correct
19 Incorrect 312 ms 13852 KB Output isn't correct
20 Correct 889 ms 10668 KB Output is correct