oj.uz

Submission #791953

# Submission time Handle Problem Language Result Execution time Memory
791953 2023-07-24T13:01:57 Z matu Job Scheduling (CEOI12_jobs) C++14
30 / 100
 199 ms 14536 KB 
#include <bits/stdc++.h>
using namespace std;
const int M = 1e6 + 1;
int n, d, m;
vector<pair<int, int>> v(M);

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> d >> m;
    for(int i = 1; i <= m; i++){
        cin >> v[i].first;
        v[i].second = i;
    }
    sort(v.begin() + 1, v.begin() + 1 + m);
    auto ok =  [&](int nrb){
        vector<int> zd;
        int st = 1, dr = 1;
        for(int i = 1; i <= n; i++){
            while(dr <= m && v[dr].first == i){
                dr++;
            }
            dr--;
            if(v[st].first + d <= i){
                return 0;
            }
            st += nrb;
            if(st > m){
                return 1;
            }
            dr = max(dr, st);
           
        }
        return 1;
    };
    auto pr =  [&](int nrb, int pl){
        vector<int> zd;
        int st = 1, dr = 1;
        for(int i = 1; i <= n; i++){
            while(dr <= m && v[dr].first == i){
                dr++;
            }
            dr--;
            for(int j = st; j < st + nrb; j++){
                if(j > m) break;
                cout << v[j].second << " ";
            }
            cout << 0 << '\n';
            st += nrb;
            dr = max(dr, st);
        }
        return;
    };
    int st = 1, dr = 1e9;
    while(st <= dr){
        int tm = (st + dr) / 2;
        if(ok(tm)){
            dr = tm - 1;
        }else st = tm + 1;
    }

    cout << st << '\n';
    pr(st, 1);
}

// 8 2 12 
// 1 2 4 2 1 3 5 6 2 3 6 4

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 8660 KB Output isn't correct
2 Incorrect 18 ms 8672 KB Output isn't correct
3 Incorrect 16 ms 8672 KB Output isn't correct
4 Incorrect 16 ms 8772 KB Output isn't correct
5 Incorrect 15 ms 8660 KB Output isn't correct
6 Incorrect 15 ms 8756 KB Output isn't correct
7 Incorrect 16 ms 8660 KB Output isn't correct
8 Incorrect 16 ms 8676 KB Output isn't correct
9 Incorrect 26 ms 8900 KB Output isn't correct
10 Incorrect 33 ms 8912 KB Output isn't correct
11 Correct 23 ms 8664 KB Output is correct
12 Incorrect 42 ms 9436 KB Output isn't correct
13 Correct 60 ms 10072 KB Output is correct
14 Incorrect 102 ms 10832 KB Output isn't correct
15 Incorrect 115 ms 11488 KB Output isn't correct
16 Correct 139 ms 12280 KB Output is correct
17 Correct 156 ms 12884 KB Output is correct
18 Correct 164 ms 13644 KB Output is correct
19 Incorrect 199 ms 14536 KB Output isn't correct
20 Correct 145 ms 12880 KB Output is correct