oj.uz

Submission #142924

# Submission time Handle Problem Language Result Execution time Memory
142924 2019-08-12T07:58:29 Z jovan_b Job Scheduling (CEOI12_jobs) C++17
43 / 100
 1000 ms 18220 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

vector <int> vec[100005];

set <pair <int, int>> q;

int n, d, m;

vector <int> resenje[100005];

bool check(int k){
    for(int i=1; i<=n; i++){
        resenje[i].clear();
    }
    for(int i=1; i<=n; i++){
        for(auto c : vec[i]){
            q.insert({i, c});
        }
        if(q.empty()) continue;
        if(q.begin()->first < i-d) return 0;
        int g = k;
        while(!q.empty() && g--){
            resenje[i].push_back(q.begin()->second);
            q.erase(q.begin());
        }
    }
    return 1;
}

int main(){
    ios_base::sync_with_stdio(false);
    cout.precision(10);
    cout<<fixed;

    cin >> n >> d >> m;
    for(int i=1; i<=m; i++){
        int x;
        cin >> x;
        vec[x].push_back(i);
    }
    int l = 1, r = m, res = m;
    while(l <= r){
        int mid = (l+r)/2;
        if(check(mid)){
            res = mid;
            r = mid-1;
        }
        else l = mid+1;
    }
    check(res);
    cout << res << "\n";
    for(int i=1; i<=n; i++){
        for(auto c : resenje[i]) cout << c << " ";
        cout << "0\n";
    }
    return 0;
}

Subtask #1
43.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 428 ms 11832 KB Partially correct
2 Partially correct 431 ms 11824 KB Partially correct
3 Partially correct 424 ms 11824 KB Partially correct
4 Partially correct 427 ms 11820 KB Partially correct
5 Partially correct 427 ms 11832 KB Partially correct
6 Partially correct 427 ms 11828 KB Partially correct
7 Partially correct 429 ms 11824 KB Partially correct
8 Partially correct 430 ms 11820 KB Partially correct
9 Correct 274 ms 8312 KB Output is correct
10 Correct 269 ms 8548 KB Output is correct
11 Correct 192 ms 7080 KB Output is correct
12 Correct 533 ms 10460 KB Output is correct
13 Partially correct 719 ms 12464 KB Partially correct
14 Correct 921 ms 18220 KB Output is correct
15 Execution timed out 1062 ms 12712 KB Time limit exceeded
16 Execution timed out 1076 ms 15736 KB Time limit exceeded
17 Execution timed out 1087 ms 18204 KB Time limit exceeded
18 Execution timed out 1046 ms 16872 KB Time limit exceeded
19 Execution timed out 1063 ms 17016 KB Time limit exceeded
20 Execution timed out 1022 ms 17816 KB Time limit exceeded