Submission #1327007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1327007		hoangtien69	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	109 ms	18748 KiB

jobs

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;

int n, d, m;
int a[MAXN];
vector<int> peal[100005];
vector<int> res[MAXN];

bool ck(int x)
{
    int cnt = 0;
    int j = 1;
    for (int i = 1; i <= n - d; i++)
    {
        int k = 0;
        if (j < i)
        {
            j = i;
            cnt = 0;
        }
        while(k < peal[i].size() and j <= n and j <= i + d)
        {
            cnt++;
            k++;
            if (cnt == x)
            {
                cnt = 0;
                j++;
            }
        }
        if (k < peal[i].size())
        {
            return false;
        }
    }
    return true;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> d >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i];
        peal[a[i]].push_back(i);
    }
    int l = 1;
    int r = m;
    int ans = -1;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        if (ck(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << ans << "\n";
    int j = 1;
    for (int i = 1; i <= n - d; i++)
    {
        int k = 0;
        j = max(j, i);
        while(k < peal[i].size() and j <= n and j <= i + d)
        {
            res[j].push_back(peal[i][k]);
            k++;
            if (res[j].size() == ans)
            {
                j++;
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (auto v : res[i])
        {
            cout << v << " ";
        }
        cout << 0 << "\n";
    }
}

• Subtask 1: 100 / 100