oj.uz

Submission #881266

# Submission time Handle Problem Language Result Execution time Memory
881266 2023-12-01T02:53:51 Z votranngocvy Job Scheduling (CEOI12_jobs) C++14
60 / 100
 219 ms 23888 KB 
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e5 + 5;
const int M = 1e6 + 5;
vector<int>vec[N];
pii a[M];
int n,d,m;

bool check(int val) {
    int day = 1,cnt = 0;
    for (int i = 1; i <= m; i++) {
        if (cnt == val) day++,cnt = 0;
        if (day < a[i].fi) day = a[i].fi,cnt = 1;
        if (day > a[i].fi && day - a[i].fi > d) return false;
        cnt++;
    }
    if (day > n) return false;
    return true;
}

int tknp(int l,int r) {
    int ans = r + 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) ans = min(ans,mid),r = mid - 1;
        else l = mid + 1;
    }
    return ans;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    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 ans = tknp(1,m);
    cout << ans << "\n";
    int day = 0,cnt = 0;
    for (int i = 1; i <= m; i++) {
        if (cnt == ans) day++,cnt = 0;
        if (day < a[i].fi) day = a[i].fi,cnt = 0;
        vec[day].push_back(a[i].se);
        cnt++;
    }
    for (int i = 1; i <= n; i++) {
        for (auto x: vec[i]) cout << x << " ";
        cout << 0 << "\n";
    }
}

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 7772 KB Output isn't correct
2 Incorrect 15 ms 7840 KB Output isn't correct
3 Incorrect 16 ms 7788 KB Output isn't correct
4 Incorrect 16 ms 7904 KB Output isn't correct
5 Incorrect 15 ms 7904 KB Output isn't correct
6 Incorrect 17 ms 7872 KB Output isn't correct
7 Incorrect 16 ms 7964 KB Output isn't correct
8 Incorrect 15 ms 7844 KB Output isn't correct
9 Correct 28 ms 8048 KB Output is correct
10 Correct 29 ms 8056 KB Output is correct
11 Correct 22 ms 7932 KB Output is correct
12 Correct 47 ms 9548 KB Output is correct
13 Correct 68 ms 13656 KB Output is correct
14 Correct 93 ms 15600 KB Output is correct
15 Correct 118 ms 15456 KB Output is correct
16 Correct 152 ms 20076 KB Output is correct
17 Correct 170 ms 23268 KB Output is correct
18 Correct 180 ms 22616 KB Output is correct
19 Correct 219 ms 23888 KB Output is correct
20 Correct 163 ms 23380 KB Output is correct