Submission #142926

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
142926	2019-08-12T08:05:08 Z	jovan_b	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	314 ms	20344 KB

jobs

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

vector <int> vec[100005];

int n, d, m;

vector <int> resenje[100005];

bool check(int k){
    queue <pair <int, int>> q;
    for(int i=1; i<=n; i++){
        resenje[i].clear();
    }
    for(int i=1; i<=n; i++){
        for(auto c : vec[i]){
            q.push({i, c});
        }
        if(q.empty()) continue;
        if(q.front().first < i-d) return 0;
        int g = k;
        while(!q.empty() && g--){
            resenje[i].push_back(q.front().second);
            q.pop();
        }
    }
    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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	36 ms	7412 KB	Output is correct
2	Correct	36 ms	7288 KB	Output is correct
3	Correct	36 ms	7284 KB	Output is correct
4	Correct	36 ms	7540 KB	Output is correct
5	Correct	36 ms	7412 KB	Output is correct
6	Correct	36 ms	7412 KB	Output is correct
7	Correct	36 ms	7412 KB	Output is correct
8	Correct	36 ms	7280 KB	Output is correct
9	Correct	45 ms	7032 KB	Output is correct
10	Correct	43 ms	7032 KB	Output is correct
11	Correct	37 ms	6648 KB	Output is correct
12	Correct	71 ms	8500 KB	Output is correct
13	Correct	102 ms	11256 KB	Output is correct
14	Correct	162 ms	13764 KB	Output is correct
15	Correct	160 ms	14200 KB	Output is correct
16	Correct	244 ms	16760 KB	Output is correct
17	Correct	301 ms	20344 KB	Output is correct
18	Correct	283 ms	19160 KB	Output is correct
19	Correct	314 ms	19892 KB	Output is correct
20	Correct	313 ms	20344 KB	Output is correct