oj.uz

Submission #374868

# Submission time Handle Problem Language Result Execution time Memory
374868 2021-03-08T11:46:09 Z Aryan_Raina Job Scheduling (CEOI12_jobs) C++14
90 / 100
 449 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; i < m; i++) {
        cout<<a[i][1]<<" ";
        if ((i+1) % hi == 0) cout<<"0\n";
    }
    if (m % hi != 0) cout<<"0\n"; 
    for (int i = (m+hi-1)/hi; i < n; i++) {
        cout<<"0\n";
    }
}

Subtask #1
90.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 2916 KB Output is correct
2 Correct 34 ms 2916 KB Output is correct
3 Correct 36 ms 2916 KB Output is correct
4 Correct 40 ms 2916 KB Output is correct
5 Correct 35 ms 2916 KB Output is correct
6 Correct 34 ms 2916 KB Output is correct
7 Correct 33 ms 2916 KB Output is correct
8 Correct 34 ms 2916 KB Output is correct
9 Correct 44 ms 2936 KB Output is correct
10 Correct 47 ms 3044 KB Output is correct
11 Correct 41 ms 2660 KB Output is correct
12 Incorrect 82 ms 5208 KB Output isn't correct
13 Correct 124 ms 7892 KB Output is correct
14 Incorrect 175 ms 10060 KB Output isn't correct
15 Correct 216 ms 12612 KB Output is correct
16 Correct 265 ms 15036 KB Output is correct
17 Correct 307 ms 17460 KB Output is correct
18 Correct 371 ms 20144 KB Output is correct
19 Correct 449 ms 22572 KB Output is correct
20 Correct 312 ms 17588 KB Output is correct