oj.uz

답안 #415373

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
415373 2021-06-01T03:03:55 Z HadiHosseini Job Scheduling (CEOI12_jobs) C++14
60 / 100
 373 ms 21456 KB 
#include <bits/stdc++.h>

using namespace std;

void show(long long cur, vector<pair<int, int>> v, int n, int d, int m) {
	int j = 0;
	for(int day = 1 ; day <= n ; day++){
		long long rev = cur;
		while(j < m && rev && v[j].first <= day){
			if(v[j].first <= day + d){
				cout << v[j].second << " ";
				rev--;
				j++;
			}
		}
		cout << "0\n";
	}
}

bool f(long long cur, vector<pair<int, int>> v, int n, int d, int m) {
	int j = 0;
	for(int day = 1 ; day <= n ; day++){
		long long rev = cur;
		while(j < m && rev && v[j].first <= day){
			if(v[j].first <= day + d && v[j].first >= day - d){
				rev--;
				j++;
			}
			else {
				return false;
			}
		}
	}
	if(j == m) return true;
	return false;
}

long long bs(vector<pair<int, int>> v, int n, int d, int m){
	long long lo = -1; long long hig = n;
	for(long long i = hig - lo; i; i /= 2){
		while(lo + i <= hig && !f(lo + i, v, n, d, m)) lo += i;
	}
	return lo + 1;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, d, m; cin >> n >> d >> m;
	vector<pair<int, int>> v(m);
	for(int i = 1 ; i <= m; i++){
		cin >> v[i - 1].first;
		v[i - 1].second = i;
	}
	sort(v.begin(), v.end());

	long long ans = bs(v, n, d, m);
	cout << ans << "\n";
	show(ans, v, n, d, m);

	return 0;
}

Subtask #1
60.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 2640 KB Output isn't correct
2 Incorrect 31 ms 2644 KB Output isn't correct
3 Incorrect 29 ms 2636 KB Output isn't correct
4 Incorrect 24 ms 2636 KB Output isn't correct
5 Incorrect 23 ms 2636 KB Output isn't correct
6 Incorrect 23 ms 2648 KB Output isn't correct
7 Incorrect 24 ms 2636 KB Output isn't correct
8 Incorrect 24 ms 2644 KB Output isn't correct
9 Correct 48 ms 2676 KB Output is correct
10 Correct 39 ms 2652 KB Output is correct
11 Correct 34 ms 2656 KB Output is correct
12 Correct 70 ms 4944 KB Output is correct
13 Correct 109 ms 7360 KB Output is correct
14 Correct 142 ms 9660 KB Output is correct
15 Correct 179 ms 12228 KB Output is correct
16 Correct 231 ms 14408 KB Output is correct
17 Correct 276 ms 16832 KB Output is correct
18 Correct 298 ms 19112 KB Output is correct
19 Correct 373 ms 21456 KB Output is correct
20 Correct 301 ms 16712 KB Output is correct