oj.uz

Submission #374876

# Submission time Handle Problem Language Result Execution time Memory
374876 2021-03-08T11:58:58 Z Aryan_Raina Job Scheduling (CEOI12_jobs) C++14
80 / 100
 411 ms 23084 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ld long double
#define ar array

const int INF = 1e15;
const int MOD = 1e9+7;

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, d, m; cin>>n>>d>>m;
    vector<ar<int,2>> a(m);
    for (int i = 0; i < m; i++) {
        cin>>a[i][0]; a[i][1] = i+1;
    }
    sort(a.begin(), a.end());

    auto check = [&](int x) {
        if ((m+x-1)/x >= n) return false;
        vector<int> time(x, 0);
        for (int i = 0; i < m; i++) {
            if (time[i % x] - a[i][0] > d) return false;
            time[i % x] = max(time[i % x], a[i][0]) + 1;
        }
        return true;
    };

    int lo = 1, hi = m, mid, x;
    while (lo < hi) {
        mid = (lo + hi)>>1;
        if (check(mid)) {
            hi = mid-1; x = mid;
        } else lo = mid+1;
    }   
    cout<<x<<"\n";
    for (int i = 0, j = 0; i < n; i++) {
        for (int k = j; j < min(k+x,m); j++) cout<<a[j][1]<<" ";
        cout<<"0\n";
    }
}

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3044 KB Output is correct
2 Correct 33 ms 3044 KB Output is correct
3 Correct 33 ms 3044 KB Output is correct
4 Correct 33 ms 3044 KB Output is correct
5 Correct 32 ms 3044 KB Output is correct
6 Correct 32 ms 3044 KB Output is correct
7 Correct 36 ms 3044 KB Output is correct
8 Correct 32 ms 3044 KB Output is correct
9 Correct 44 ms 3172 KB Output is correct
10 Correct 43 ms 3044 KB Output is correct
11 Correct 41 ms 2788 KB Output is correct
12 Incorrect 81 ms 5336 KB Output isn't correct
13 Correct 122 ms 7764 KB Output is correct
14 Incorrect 169 ms 10316 KB Output isn't correct
15 Incorrect 221 ms 12664 KB Output isn't correct
16 Correct 280 ms 15164 KB Output is correct
17 Correct 310 ms 17716 KB Output is correct
18 Incorrect 362 ms 20284 KB Output isn't correct
19 Correct 411 ms 23084 KB Output is correct
20 Correct 309 ms 17824 KB Output is correct