oj.uz

답안 #810853

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
810853 2023-08-06T16:44:40 Z khanghb2006 Job Scheduling (CEOI12_jobs) C++17
75 / 100
 103 ms 9420 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
#define MASK(n) (1 << (n))
#define BIT(mask,x) ((mask >> (x)) & 1)
#define TASK "task"

using namespace std;
const int mxN = 5e5 + 7;
const int base = 512;
const int inf = 1e9 + 6969;
const int Mod = 1e9 + 7;
const long long infll = 1e18 + 6969;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
     if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
     if (a < b) {a = b; return true;} return false;
}

int n;
int d;
int m;
pair<int,int>a[mxN];

bool ok(int num_machine) {
	int j = 1;
	int cnt;
	for (int i = 1; i <= n; i++) {
		cnt = 0;
		if(a[j].fi + d < i) {
			//cout << i << " " << j << "\n";
			return false;
		}
		while(cnt < num_machine && a[j].fi <= i && j <= m) {
			cnt++; 
			j++;
		}
		if(j > m) return true;
	}
	return false;
}

void tracing(int num_machine) {
	int j = 1;
	int cnt;
	for (int i = 1; i <= n; i++) {
		cnt = 0;
		while(cnt < num_machine && a[j].fi <= i && j <= m) {
			cnt++;
			cout << a[j].se << " ";
			j++;
		}
		cout << 0 << '\n';
	}
}

void solve() {
	cin >> n >> d >> m;
	for (int i = 1; i <= m; i++) cin >> a[i].fi,a[i].se = i;
	sort(a + 1,a + m + 1);
	int lo = 1,hi = max(n,m),ans = 0;
	while(lo <= hi) {
		int mid = (lo + hi) >> 1;
		if(ok(mid)) {
			ans = mid;
			hi = mid - 1;
		}else lo = mid + 1;
	}
	cout << ans << "\n";
	tracing(ans);
}

signed main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	int tc = 1;
	//cin >> tc;
	while(tc--) {
		solve();
	}
}

Subtask #1
75.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 2004 KB Output is correct
2 Correct 13 ms 1916 KB Output is correct
3 Correct 15 ms 2004 KB Output is correct
4 Correct 14 ms 1936 KB Output is correct
5 Correct 13 ms 1988 KB Output is correct
6 Correct 14 ms 2008 KB Output is correct
7 Correct 13 ms 1924 KB Output is correct
8 Correct 16 ms 1932 KB Output is correct
9 Correct 25 ms 2128 KB Output is correct
10 Correct 27 ms 2124 KB Output is correct
11 Correct 21 ms 1972 KB Output is correct
12 Correct 53 ms 3848 KB Output is correct
13 Correct 61 ms 5736 KB Output is correct
14 Correct 88 ms 8012 KB Output is correct
15 Correct 103 ms 9420 KB Output is correct
16 Incorrect 36 ms 6788 KB Output isn't correct
17 Incorrect 30 ms 6716 KB Output isn't correct
18 Incorrect 26 ms 6380 KB Output isn't correct
19 Incorrect 31 ms 6508 KB Output isn't correct
20 Incorrect 30 ms 6796 KB Output isn't correct