oj.uz

Submission #988489

# Submission time Handle Problem Language Result Execution time Memory
988489 2024-05-25T03:21:45 Z hansenhe Job Scheduling (CEOI12_jobs) C++14
55 / 100
 40 ms 9756 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, d, m;
pair<int, int> req[100005];
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
55.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4980 KB Output is correct
2 Correct 28 ms 5012 KB Output is correct
3 Correct 28 ms 5016 KB Output is correct
4 Correct 27 ms 5008 KB Output is correct
5 Correct 27 ms 5012 KB Output is correct
6 Correct 27 ms 5012 KB Output is correct
7 Correct 27 ms 5012 KB Output is correct
8 Correct 27 ms 5012 KB Output is correct
9 Correct 38 ms 9756 KB Output is correct
10 Correct 40 ms 9624 KB Output is correct
11 Correct 33 ms 5068 KB Output is correct
12 Incorrect 6 ms 2652 KB Output isn't correct
13 Incorrect 6 ms 2648 KB Output isn't correct
14 Incorrect 13 ms 3424 KB Output isn't correct
15 Incorrect 6 ms 1880 KB Output isn't correct
16 Incorrect 10 ms 3184 KB Output isn't correct
17 Incorrect 15 ms 3436 KB Output isn't correct
18 Incorrect 10 ms 3180 KB Output isn't correct
19 Incorrect 16 ms 7476 KB Output isn't correct
20 Incorrect 14 ms 3440 KB Output isn't correct