oj.uz

답안 #142926

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
142926 2019-08-12T08:05:08 Z jovan_b Job Scheduling (CEOI12_jobs) C++17
100 / 100
 314 ms 20344 KB 
#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

# 결과 실행 시간 메모리 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