제출 #1345863

#제출 시각아이디문제언어결과실행 시간메모리
1345863thaibaotran555Job Scheduling (CEOI12_jobs)C++20
100 / 100
127 ms13884 KiB
///TRAN THAI BAO :3

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef pair<int, int> pii;

#define maxN 1000007

int n, m, d;
pii a[maxN];

bool check(int k)
{
    int i = 1;
    int day = 1;
    while(day <= n && i <= m)
    {
        for(int j = 1; j <= k; j++)
        {
            if(i > m)
                return true;
            if(a[i].first <= day)
            {
                if(day - a[i].first > d)
                    return false;
                i++;
            }
            else break;
        }
        day++;
    }
    if(i > m)
        return true;
    return false;
}

void getAns(int k)
{
    int i = 1;
    int day = 1;
    while(day <= n)
    {
        for(int j = 1; j <= k; j++)
        {
            if(i > m)
                break;
            if(a[i].first <= day)
            {
                cout << a[i].second << ' ';
                i++;
            }
            else break;
        }
        cout << "0\n";
        day++;
    }
}

void solve()
{
    cin >> n >> d >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a+1, a+m+1);
    int lo = 1, hi = m, mid, minAns = m;
    while(lo <= hi)
    {
        mid = (lo+hi)/2;
        if(check(mid))
        {
            hi = mid-1;
            minAns = min(minAns, mid);
        }
        else lo = mid+1;
    }
    cout << minAns << '\n';
    getAns(minAns);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...