oj.uz

Submission #97642

# Submission time Handle Problem Language Result Execution time Memory
97642 2019-02-17T15:37:28 Z dalgerok Job Scheduling (CEOI12_jobs) C++14
75 / 100
 1000 ms 17124 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 36 ms 7508 KB Output is correct
2 Correct 30 ms 7508 KB Output is correct
3 Correct 32 ms 7508 KB Output is correct
4 Correct 31 ms 7504 KB Output is correct
5 Correct 33 ms 7480 KB Output is correct
6 Correct 32 ms 7616 KB Output is correct
7 Correct 36 ms 7508 KB Output is correct
8 Correct 31 ms 7508 KB Output is correct
9 Correct 45 ms 7928 KB Output is correct
10 Correct 51 ms 7800 KB Output is correct
11 Correct 64 ms 7544 KB Output is correct
12 Correct 148 ms 10016 KB Output is correct
13 Correct 219 ms 13688 KB Output is correct
14 Correct 379 ms 16640 KB Output is correct
15 Correct 791 ms 17124 KB Output is correct
16 Execution timed out 1064 ms 16120 KB Time limit exceeded
17 Execution timed out 1071 ms 15772 KB Time limit exceeded
18 Execution timed out 1061 ms 15708 KB Time limit exceeded
19 Execution timed out 1055 ms 16616 KB Time limit exceeded
20 Execution timed out 1072 ms 15768 KB Time limit exceeded