oj.uz

Submission #374863

# Submission time Handle Problem Language Result Execution time Memory
374863 2021-03-08T11:42:40 Z Aryan_Raina Job Scheduling (CEOI12_jobs) C++14
25 / 100
 414 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] = 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
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 2660 KB Output isn't correct
2 Incorrect 37 ms 2660 KB Output isn't correct
3 Incorrect 36 ms 2680 KB Output isn't correct
4 Incorrect 34 ms 2660 KB Output isn't correct
5 Incorrect 36 ms 2756 KB Output isn't correct
6 Incorrect 38 ms 2720 KB Output isn't correct
7 Incorrect 34 ms 2660 KB Output isn't correct
8 Incorrect 33 ms 2660 KB Output isn't correct
9 Incorrect 47 ms 2916 KB Output isn't correct
10 Incorrect 47 ms 3064 KB Output isn't correct
11 Correct 43 ms 2788 KB Output is correct
12 Incorrect 85 ms 5208 KB Output isn't correct
13 Correct 131 ms 7764 KB Output is correct
14 Incorrect 182 ms 10080 KB Output isn't correct
15 Incorrect 220 ms 12612 KB Output isn't correct
16 Correct 278 ms 15036 KB Output is correct
17 Correct 310 ms 17440 KB Output is correct
18 Incorrect 359 ms 20152 KB Output isn't correct
19 Incorrect 414 ms 22572 KB Output isn't correct
20 Correct 314 ms 17440 KB Output is correct