oj.uz

답안 #640405

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
640405 2022-09-14T14:54:41 Z AmirH Job Scheduling (CEOI12_jobs) C++14
30 / 100
 1000 ms 12240 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()) {
				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

# 결과 실행 시간 메모리 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