Submission #640405

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
640405	2022-09-14T14:54:41 Z	AmirH	Job Scheduling (CEOI12_jobs)	C++14	30 / 100	1000 ms	12240 KB

jobs

#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()) {
				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()) {
				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: In function 'bool check(int)':
jobs.cpp:39: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]
   39 |    if(p < v.size()) {
      |       ~~^~~~~~~~~~

Subtask #1

30.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1085 ms	1492 KB	Time limit exceeded
2	Execution timed out	1087 ms	1492 KB	Time limit exceeded
3	Execution timed out	1091 ms	1492 KB	Time limit exceeded
4	Execution timed out	1084 ms	1492 KB	Time limit exceeded
5	Execution timed out	1087 ms	1492 KB	Time limit exceeded
6	Execution timed out	1084 ms	1492 KB	Time limit exceeded
7	Execution timed out	1093 ms	1492 KB	Time limit exceeded
8	Execution timed out	1095 ms	1492 KB	Time limit exceeded
9	Execution timed out	1087 ms	1492 KB	Time limit exceeded
10	Execution timed out	1096 ms	1492 KB	Time limit exceeded
11	Correct	98 ms	1792 KB	Output is correct
12	Incorrect	124 ms	3296 KB	Output isn't correct
13	Correct	173 ms	4712 KB	Output is correct
14	Incorrect	913 ms	6348 KB	Output isn't correct
15	Incorrect	205 ms	7680 KB	Output isn't correct
16	Correct	835 ms	9236 KB	Output is correct
17	Correct	887 ms	10668 KB	Output is correct
18	Correct	971 ms	12240 KB	Output is correct
19	Execution timed out	1095 ms	8648 KB	Time limit exceeded
20	Correct	950 ms	10928 KB	Output is correct