Submission #791934

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
791934	2023-07-24T12:40:42 Z	matu	Job Scheduling (CEOI12_jobs)	C++14	15 / 100	182 ms	14504 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 && 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 = 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

15.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	16 ms	8660 KB	Output isn't correct
2	Incorrect	16 ms	8756 KB	Output isn't correct
3	Incorrect	16 ms	8660 KB	Output isn't correct
4	Incorrect	17 ms	8688 KB	Output isn't correct
5	Incorrect	16 ms	8672 KB	Output isn't correct
6	Incorrect	16 ms	8748 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	8928 KB	Output isn't correct
10	Incorrect	26 ms	8932 KB	Output isn't correct
11	Incorrect	22 ms	8676 KB	Output isn't correct
12	Correct	41 ms	9436 KB	Output is correct
13	Incorrect	62 ms	10064 KB	Output isn't correct
14	Correct	103 ms	10828 KB	Output is correct
15	Incorrect	99 ms	11468 KB	Output isn't correct
16	Correct	123 ms	12236 KB	Output is correct
17	Incorrect	162 ms	12880 KB	Output isn't correct
18	Incorrect	159 ms	13664 KB	Output isn't correct
19	Incorrect	182 ms	14504 KB	Output isn't correct
20	Incorrect	142 ms	12888 KB	Output isn't correct