Submission #791945

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
791945	2023-07-24T12:46:29 Z	matu	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	183 ms	14668 KB

jobs

#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--;
            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 = 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

55.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	16 ms	8780 KB	Output isn't correct
2	Incorrect	16 ms	8812 KB	Output isn't correct
3	Incorrect	19 ms	8844 KB	Output isn't correct
4	Incorrect	16 ms	8788 KB	Output isn't correct
5	Incorrect	15 ms	8792 KB	Output isn't correct
6	Incorrect	16 ms	8784 KB	Output isn't correct
7	Incorrect	16 ms	8788 KB	Output isn't correct
8	Incorrect	16 ms	8812 KB	Output isn't correct
9	Correct	26 ms	9072 KB	Output is correct
10	Correct	28 ms	9060 KB	Output is correct
11	Correct	21 ms	8700 KB	Output is correct
12	Correct	40 ms	9480 KB	Output is correct
13	Correct	59 ms	10108 KB	Output is correct
14	Correct	99 ms	10952 KB	Output is correct
15	Incorrect	99 ms	11600 KB	Output isn't correct
16	Correct	122 ms	12284 KB	Output is correct
17	Correct	143 ms	13028 KB	Output is correct
18	Correct	172 ms	13760 KB	Output is correct
19	Correct	183 ms	14668 KB	Output is correct
20	Correct	145 ms	13120 KB	Output is correct