oj.uz

Submission #97644

# Submission time Handle Problem Language Result Execution time Memory
97644 2019-02-17T15:39:13 Z dalgerok Job Scheduling (CEOI12_jobs) C++17
75 / 100
 1000 ms 20224 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[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
75.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 7508 KB Output is correct
2 Correct 31 ms 7632 KB Output is correct
3 Correct 39 ms 7636 KB Output is correct
4 Correct 34 ms 7504 KB Output is correct
5 Correct 37 ms 7508 KB Output is correct
6 Correct 36 ms 7504 KB Output is correct
7 Correct 36 ms 7660 KB Output is correct
8 Correct 38 ms 7580 KB Output is correct
9 Correct 47 ms 7800 KB Output is correct
10 Correct 60 ms 7928 KB Output is correct
11 Correct 57 ms 7544 KB Output is correct
12 Correct 150 ms 9976 KB Output is correct
13 Correct 279 ms 13688 KB Output is correct
14 Correct 359 ms 16540 KB Output is correct
15 Correct 770 ms 17236 KB Output is correct
16 Execution timed out 1066 ms 20224 KB Time limit exceeded
17 Execution timed out 1046 ms 15736 KB Time limit exceeded
18 Execution timed out 1049 ms 15740 KB Time limit exceeded
19 Execution timed out 1070 ms 16504 KB Time limit exceeded
20 Execution timed out 1082 ms 15872 KB Time limit exceeded