oj.uz

Submission #441764

# Submission time Handle Problem Language Result Execution time Memory
441764 2021-07-06T04:00:53 Z Yuisuyuno Job Scheduling (CEOI12_jobs) C++14
70 / 100
 526 ms 40648 KB 
//Nguyen Huu Hoang Minh
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define N 1000001
#define ii pair<int, int>
#define vi vector<int>
#define int long long

using namespace std;
const int minf = -1e10;

vector<int> res[100012];
int n, m, d;

bool ok(int machine, vector<ii> a){
    int delays=0;
    int en[machine] = {0};
    for(int i=0, cur=0; i<m; i++, cur++){
        if (cur==machine) cur=0;
        if (en[cur] + 1 > a[i].fi){
            en[cur]++;
            delays = max(delays,en[cur]-a[i].fi);
        }
        else en[cur] = a[i].fi;
    }
    return delays <= d;
}

signed main()
{
    vector<ii> a;
    cin >> n >> d >> m;
    a.resize(m);
    for(int i=0; i<m; i++){
        cin >> a[i].fi;
        a[i].se = i+1;
    }
    sort(a.begin(),a.end());
    int l = 0, r = m;
    int ans;
    while (r-l > 0){
        int mid = (l+r)/2;
        if (ok(mid,a)){
            ans = mid;
            r = mid-1;
        }
        else l = mid+1;
    }
    cout<<ans<<'\n';
    int en[ans] = {0};
    for(int i=0, cur=0; i<m; i++, cur++){
        if (cur==ans) cur=0;
        en[cur] = max(en[cur]+1,a[i].fi);
        res[en[cur]].pb(a[i].se);
    }
    for(int i=1; i<=n; i++){
        for(int x : res[i]) cout << x << ' ';
        cout << "0\n";
    }
    return 0;
}

Subtask #1
70.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 6712 KB Output is correct
2 Correct 43 ms 6696 KB Output is correct
3 Correct 43 ms 6724 KB Output is correct
4 Correct 43 ms 6664 KB Output is correct
5 Correct 43 ms 6744 KB Output is correct
6 Correct 44 ms 6652 KB Output is correct
7 Correct 50 ms 6736 KB Output is correct
8 Correct 46 ms 6748 KB Output is correct
9 Correct 53 ms 6876 KB Output is correct
10 Correct 54 ms 6888 KB Output is correct
11 Incorrect 55 ms 6744 KB Output isn't correct
12 Correct 109 ms 10916 KB Output is correct
13 Incorrect 166 ms 15180 KB Output isn't correct
14 Incorrect 239 ms 19392 KB Output isn't correct
15 Correct 295 ms 23572 KB Output is correct
16 Incorrect 369 ms 27812 KB Output isn't correct
17 Correct 427 ms 32116 KB Output is correct
18 Runtime error 460 ms 36348 KB Memory limit exceeded
19 Runtime error 526 ms 40648 KB Memory limit exceeded
20 Correct 436 ms 32028 KB Output is correct