oj.uz

Submission #988491

# Submission time Handle Problem Language Result Execution time Memory
988491 2024-05-25T03:28:25 Z hansenhe Job Scheduling (CEOI12_jobs) C++14
100 / 100
 311 ms 27032 KB 
#include <bits/stdc++.h>
using namespace std;
int n, d, m;
pair<int, int> req[1000005];
vector<vector<int>> out;
bool good(int mach){
    vector<vector<int>> each(n + 1);
    vector<int> day(mach + 1);
    int cur = 1;
    for (int i = 0; i < m; i++){
        day[cur] = max(day[cur] + 1, req[i].first);
        each[day[cur]].push_back(req[i].second);
        if (day[cur] - req[i].first > d){
            return false;
        }
        cur++;
        cur %= mach;
        if (cur == 0) cur = mach;
    }
    out = each;
    return true;
}
signed main(){
    ios::sync_with_stdio(false);
	cin.tie(nullptr);
	// freopen("split.in", "r", stdin);
	// freopen("split.out", "w", stdout);
    cin >> n >> d >> m;
    for (int i = 0; i < m; i++){
        cin >> req[i].first;
        req[i].second = i + 1;
    }
    sort(req, req + m);
    int a = 1, b = m;
    while (a != b){
        int mid = (a + b) / 2;
        if (good(mid)){
            b = mid;
        } else {
            a = mid + 1;
        }
    }
    cout << a << "\n";
    for (int i = 1; i <= n; i++){
        for (int x : out[i]){
            cout << x << " ";
        }
        cout << "0\n";
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4460 KB Output is correct
2 Correct 24 ms 4424 KB Output is correct
3 Correct 23 ms 4408 KB Output is correct
4 Correct 23 ms 4460 KB Output is correct
5 Correct 24 ms 4380 KB Output is correct
6 Correct 23 ms 4460 KB Output is correct
7 Correct 23 ms 4408 KB Output is correct
8 Correct 23 ms 4408 KB Output is correct
9 Correct 36 ms 9308 KB Output is correct
10 Correct 37 ms 9296 KB Output is correct
11 Correct 31 ms 4248 KB Output is correct
12 Correct 63 ms 5908 KB Output is correct
13 Correct 91 ms 10232 KB Output is correct
14 Correct 143 ms 12620 KB Output is correct
15 Correct 147 ms 13372 KB Output is correct
16 Correct 219 ms 17916 KB Output is correct
17 Correct 239 ms 20748 KB Output is correct
18 Correct 253 ms 20652 KB Output is correct
19 Correct 311 ms 27032 KB Output is correct
20 Correct 238 ms 20772 KB Output is correct