oj.uz

Submission #374878

# Submission time Handle Problem Language Result Execution time Memory
374878 2021-03-08T12:02:14 Z Aryan_Raina Job Scheduling (CEOI12_jobs) C++14
100 / 100
 407 ms 22572 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 = 0, hi = m, mid;
    while (lo + 1 < hi) {
        mid = (lo + hi)>>1;
        if (check(mid)) hi = mid;
        else lo = mid;
    }   
    cout<<hi<<"\n";
    for (int i = 0, j = 0; i < n; i++) {
        for (int k = j; j < min(k+hi,m); j++) cout<<a[j][1]<<" ";
        cout<<"0\n";
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2916 KB Output is correct
2 Correct 32 ms 2916 KB Output is correct
3 Correct 33 ms 2916 KB Output is correct
4 Correct 33 ms 2916 KB Output is correct
5 Correct 32 ms 2916 KB Output is correct
6 Correct 33 ms 2916 KB Output is correct
7 Correct 32 ms 2916 KB Output is correct
8 Correct 32 ms 2916 KB Output is correct
9 Correct 44 ms 2916 KB Output is correct
10 Correct 43 ms 3044 KB Output is correct
11 Correct 41 ms 2660 KB Output is correct
12 Correct 86 ms 5208 KB Output is correct
13 Correct 130 ms 7636 KB Output is correct
14 Correct 176 ms 10060 KB Output is correct
15 Correct 220 ms 12620 KB Output is correct
16 Correct 258 ms 15036 KB Output is correct
17 Correct 313 ms 17460 KB Output is correct
18 Correct 368 ms 20144 KB Output is correct
19 Correct 407 ms 22572 KB Output is correct
20 Correct 316 ms 17460 KB Output is correct