oj.uz

Submission #97643

# Submission time Handle Problem Language Result Execution time Memory
97643 2019-02-17T15:38:34 Z dalgerok Job Scheduling (CEOI12_jobs) C++17
60 / 100
 381 ms 33792 KB 
#include<bits/stdc++.h>
using namespace std;


const int N = 1e5 + 5;




int n, d, m, a[10 * N], ans[10 * N];
vector < int > q[10 * N], s[N];


inline bool check(int x){
    queue < int > e;
    for(int i = 1; i <= n; i++){
        for(auto it : q[i]){
            e.push(it);
        }
        for(int j = 1; j <= x && !e.empty(); j++){
            if(a[e.front()] + d < i){
                return false;
            }
            ans[e.front()] = i;
            e.pop();
        }
    }
    return e.empty();
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> d >> m;
    for(int i = 1; i <= m; i++){
        cin >> a[i];
        q[a[i]].push_back(i);
    }
    int l = 1, r = m;
    while(l < r){
        int mid = (r + l) >> 1;
        if(check(mid)){
            r = mid;
        }
        else{
            l = mid + 1;
        }
    }
    check(l);
    for(int i = 1; i <= m; i++){
        s[ans[i]].push_back(i);
    }
    cout << l << "\n";
    for(int i = 1; i <= n; i++){
        for(auto it : s[i]){
            cout << it << " ";
        }
        cout << "0\n";
    }
}

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 28628 KB Output is correct
2 Correct 63 ms 28912 KB Output is correct
3 Correct 60 ms 28608 KB Output is correct
4 Correct 55 ms 28628 KB Output is correct
5 Correct 63 ms 28628 KB Output is correct
6 Correct 57 ms 28628 KB Output is correct
7 Correct 53 ms 28628 KB Output is correct
8 Correct 69 ms 28708 KB Output is correct
9 Correct 73 ms 28896 KB Output is correct
10 Correct 73 ms 29096 KB Output is correct
11 Correct 99 ms 28720 KB Output is correct
12 Correct 158 ms 31132 KB Output is correct
13 Runtime error 252 ms 33792 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
14 Runtime error 305 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 381 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 138 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 172 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 127 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 115 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 194 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)