oj.uz

Submission #374873

# Submission time Handle Problem Language Result Execution time Memory
374873 2021-03-08T11:54:54 Z Aryan_Raina Job Scheduling (CEOI12_jobs) C++14
90 / 100
 404 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
90.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2916 KB Output is correct
2 Correct 33 ms 2916 KB Output is correct
3 Correct 34 ms 2916 KB Output is correct
4 Correct 127 ms 2916 KB Output is correct
5 Correct 35 ms 2916 KB Output is correct
6 Correct 124 ms 2916 KB Output is correct
7 Correct 147 ms 2916 KB Output is correct
8 Correct 33 ms 2916 KB Output is correct
9 Correct 46 ms 2916 KB Output is correct
10 Correct 42 ms 2916 KB Output is correct
11 Correct 42 ms 2720 KB Output is correct
12 Incorrect 81 ms 5212 KB Output isn't correct
13 Correct 204 ms 7636 KB Output is correct
14 Incorrect 268 ms 10060 KB Output isn't correct
15 Correct 318 ms 12612 KB Output is correct
16 Correct 264 ms 15036 KB Output is correct
17 Correct 299 ms 17460 KB Output is correct
18 Correct 374 ms 20016 KB Output is correct
19 Correct 404 ms 22572 KB Output is correct
20 Correct 302 ms 17460 KB Output is correct