oj.uz

답안 #533091

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
533091 2022-03-04T18:04:26 Z Bench0310 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 274 ms 22748 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,d,m;
    cin >> n >> d >> m;
    vector<int> v[n+1];
    for(int i=1;i<=m;i++)
    {
        int x;
        cin >> x;
        v[x].push_back(i);
    }
    vector<vector<int>> res(n+1);
    auto go=[&](int lim)->bool
    {
        vector<int> cnt(n+1,0);
        int idx=n;
        res.assign(n+1,{});
        for(int i=n;i>=1;i--)
        {
            for(int id:v[i])
            {
                while(idx>i+d||cnt[idx]==lim) idx--;
                if(idx==i-1) return 0;
                res[idx].push_back(id);
                cnt[idx]++;
            }
        }
        return 1;
    };
    int l=0,r=m;
    while(l<r-1)
    {
        int lim=(l+r)/2;
        if(go(lim)) r=lim;
        else l=lim;
    }
    cout << r << "\n";
    go(r);
    for(int i=1;i<=n;i++)
    {
        for(int id:res[i]) cout << id << " ";
        cout << "0\n";
    }
    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 2756 KB Output is correct
2 Correct 27 ms 2696 KB Output is correct
3 Correct 29 ms 2668 KB Output is correct
4 Correct 36 ms 2752 KB Output is correct
5 Correct 27 ms 2696 KB Output is correct
6 Correct 35 ms 2700 KB Output is correct
7 Correct 29 ms 2680 KB Output is correct
8 Correct 33 ms 2676 KB Output is correct
9 Correct 61 ms 7552 KB Output is correct
10 Correct 45 ms 7600 KB Output is correct
11 Correct 27 ms 2368 KB Output is correct
12 Correct 57 ms 4348 KB Output is correct
13 Correct 90 ms 7636 KB Output is correct
14 Correct 126 ms 10632 KB Output is correct
15 Correct 154 ms 11228 KB Output is correct
16 Correct 175 ms 14768 KB Output is correct
17 Correct 225 ms 18976 KB Output is correct
18 Correct 249 ms 17476 KB Output is correct
19 Correct 274 ms 22748 KB Output is correct
20 Correct 232 ms 19064 KB Output is correct