oj.uz

Submission #97640

# Submission time Handle Problem Language Result Execution time Memory
97640 2019-02-17T15:35:48 Z dalgerok Job Scheduling (CEOI12_jobs) C++17
55 / 100
 71 ms 8056 KB 
#include<bits/stdc++.h>
using namespace std;


const int N = 1e5 + 5;




int n, d, m, a[N], ans[N];
vector < int > q[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
55.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 7772 KB Output is correct
2 Correct 36 ms 7764 KB Output is correct
3 Correct 34 ms 7768 KB Output is correct
4 Correct 41 ms 7760 KB Output is correct
5 Correct 35 ms 7764 KB Output is correct
6 Correct 36 ms 7764 KB Output is correct
7 Correct 37 ms 7892 KB Output is correct
8 Correct 35 ms 7764 KB Output is correct
9 Correct 46 ms 8056 KB Output is correct
10 Correct 48 ms 8028 KB Output is correct
11 Correct 71 ms 7928 KB Output is correct
12 Incorrect 40 ms 7224 KB Output isn't correct
13 Incorrect 17 ms 6912 KB Output isn't correct
14 Incorrect 54 ms 7296 KB Output isn't correct
15 Incorrect 29 ms 7032 KB Output isn't correct
16 Incorrect 53 ms 7388 KB Output isn't correct
17 Incorrect 52 ms 7388 KB Output isn't correct
18 Incorrect 36 ms 7032 KB Output isn't correct
19 Incorrect 44 ms 7288 KB Output isn't correct
20 Incorrect 58 ms 7368 KB Output isn't correct