Submission #462451

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
462451	2021-08-10T14:49:04 Z	JovanB	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	334 ms	21168 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	35 ms	7496 KB	Output is correct
2	Correct	33 ms	7492 KB	Output is correct
3	Correct	34 ms	7500 KB	Output is correct
4	Correct	37 ms	7516 KB	Output is correct
5	Correct	35 ms	7496 KB	Output is correct
6	Correct	64 ms	7544 KB	Output is correct
7	Correct	36 ms	7508 KB	Output is correct
8	Correct	43 ms	7568 KB	Output is correct
9	Correct	41 ms	7168 KB	Output is correct
10	Correct	44 ms	7252 KB	Output is correct
11	Correct	33 ms	7072 KB	Output is correct
12	Correct	66 ms	9000 KB	Output is correct
13	Correct	153 ms	11708 KB	Output is correct
14	Correct	159 ms	14020 KB	Output is correct
15	Correct	161 ms	14728 KB	Output is correct
16	Correct	212 ms	17020 KB	Output is correct
17	Correct	264 ms	21132 KB	Output is correct
18	Correct	283 ms	19832 KB	Output is correct
19	Correct	334 ms	20684 KB	Output is correct
20	Correct	312 ms	21168 KB	Output is correct