oj.uz

Submission #441765

# Submission time Handle Problem Language Result Execution time Memory
441765 2021-07-06T04:04:56 Z Yuisuyuno Job Scheduling (CEOI12_jobs) C++14
100 / 100
 500 ms 24992 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>

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

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;
}

int 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)){
            r = mid;
        }
        else l = mid+1;
    }
    cout<<l<<'\n';
    int endT[l]={0};
    for(int i=0, cur=0; i<m; i++, cur++){
        if (cur==l) cur=0;
        endT[cur] = max(endT[cur]+1,a[i].fi);
        res[endT[cur]].pb(a[i].se);
    }
    for(int i=1; i<=n; i++){
        for(int x : res[i]) cout << x << ' ';
        cout << "0\n";
    }
    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:41:9: warning: unused variable 'ans' [-Wunused-variable]
   41 |     int ans;
      |         ^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 4916 KB Output is correct
2 Correct 43 ms 4972 KB Output is correct
3 Correct 41 ms 4936 KB Output is correct
4 Correct 41 ms 4996 KB Output is correct
5 Correct 44 ms 4912 KB Output is correct
6 Correct 41 ms 4944 KB Output is correct
7 Correct 41 ms 4948 KB Output is correct
8 Correct 42 ms 4972 KB Output is correct
9 Correct 53 ms 5172 KB Output is correct
10 Correct 53 ms 5076 KB Output is correct
11 Correct 52 ms 4948 KB Output is correct
12 Correct 108 ms 7384 KB Output is correct
13 Correct 160 ms 9808 KB Output is correct
14 Correct 237 ms 12360 KB Output is correct
15 Correct 269 ms 14840 KB Output is correct
16 Correct 348 ms 17260 KB Output is correct
17 Correct 417 ms 19740 KB Output is correct
18 Correct 439 ms 22220 KB Output is correct
19 Correct 500 ms 24992 KB Output is correct
20 Correct 407 ms 19672 KB Output is correct