oj.uz

Submission #988490

# Submission time Handle Problem Language Result Execution time Memory
988490 2024-05-25T03:27:42 Z hansenhe Job Scheduling (CEOI12_jobs) C++14
80 / 100
 340 ms 42856 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
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
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5684 KB Output is correct
2 Correct 29 ms 5708 KB Output is correct
3 Correct 28 ms 5676 KB Output is correct
4 Correct 27 ms 5680 KB Output is correct
5 Correct 27 ms 5684 KB Output is correct
6 Correct 35 ms 5672 KB Output is correct
7 Correct 26 ms 5680 KB Output is correct
8 Correct 27 ms 5672 KB Output is correct
9 Correct 38 ms 10340 KB Output is correct
10 Correct 39 ms 10400 KB Output is correct
11 Correct 32 ms 5388 KB Output is correct
12 Correct 63 ms 10036 KB Output is correct
13 Correct 95 ms 15536 KB Output is correct
14 Correct 153 ms 19268 KB Output is correct
15 Correct 163 ms 22224 KB Output is correct
16 Correct 219 ms 27964 KB Output is correct
17 Runtime error 289 ms 35292 KB Memory limit exceeded
18 Runtime error 300 ms 36952 KB Memory limit exceeded
19 Runtime error 340 ms 42856 KB Memory limit exceeded
20 Runtime error 287 ms 35288 KB Memory limit exceeded