oj.uz

Submission #791928

# Submission time Handle Problem Language Result Execution time Memory
791928 2023-07-24T12:38:04 Z matu Job Scheduling (CEOI12_jobs) C++14
15 / 100
 218 ms 15152 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 && st <= m && dr <= m; i++){
            while(dr <= m && v[dr].first == i){
                dr++;
            }
            dr--;
            st += nrb;
            if(st > m){
                return 1;
            }
            dr = max(dr, st);
            if(v[st].first + d < i){
                return 0;
            }
        }
        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 = m;
    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
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 8788 KB Output isn't correct
2 Incorrect 16 ms 8792 KB Output isn't correct
3 Incorrect 16 ms 8852 KB Output isn't correct
4 Incorrect 19 ms 8828 KB Output isn't correct
5 Incorrect 16 ms 8808 KB Output isn't correct
6 Incorrect 16 ms 8792 KB Output isn't correct
7 Incorrect 16 ms 8788 KB Output isn't correct
8 Incorrect 16 ms 8788 KB Output isn't correct
9 Incorrect 28 ms 9072 KB Output isn't correct
10 Incorrect 26 ms 9088 KB Output isn't correct
11 Incorrect 23 ms 8720 KB Output isn't correct
12 Correct 42 ms 9420 KB Output is correct
13 Incorrect 60 ms 10188 KB Output isn't correct
14 Correct 83 ms 11084 KB Output is correct
15 Incorrect 98 ms 11492 KB Output isn't correct
16 Correct 123 ms 12476 KB Output is correct
17 Incorrect 158 ms 13124 KB Output isn't correct
18 Incorrect 168 ms 13768 KB Output isn't correct
19 Incorrect 218 ms 15152 KB Output isn't correct
20 Incorrect 145 ms 13176 KB Output isn't correct