Submission #708520

#	Time	Username	Problem	Language	Result	Execution time	Memory
708520		jsathu07	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	341 ms	41116 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;

pair<bool, vector<vector<int>>> calc(int n, int d, int x, vector<pair<int, int>> &brr, int m)
{
    int j = 0;
    bool p = true;
    vector<vector<int>> temp(n);
    for (int i = 0; i < n; i++)
    {
        int y = x;
        while (y-- && j < m)
        {
            if (!(i + 1 <= brr[j].first + d))
            {
                p = false;
                break;
            }
            temp[i].push_back(brr[j].second);
            // cout << "day " << i + 1 << " processed " << j + 1 << " \n";
            j++;
        }
        if (!p)
            break;
    }
    return {p, temp};
}

void solve()
{
    int n, d, m;
    cin >> n >> d >> m;
    vector<pair<int, int>> brr;
    for (int i = 0; i < m; i++)
    {
        int x;
        cin >> x;
        brr.push_back({x, i + 1});
    }
    sort(brr.begin(), brr.end());
    int l = 1, r = 1e6, ans = 1e6;
    vector<vector<int>> ansvec;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        pair<bool, vector<vector<int>>> temp = calc(n, d, mid, brr, m);
        if (temp.first)
        {
            ans = mid;
            ansvec = temp.second;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << ans << "\n";
    // for (auto &i : ansvec)
    // {
    //     if (!i.empty())
    //     {
    //         for (auto &j : i)
    //             cout << j << " ";
    //     }
    //     cout << 0 << "\n";
    // }
}

// void setIO(string s)
// {
//     freopen((s + ".in").c_str(), "r", stdin);
//     freopen((s + ".out").c_str(), "w", stdout);
// }

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

• Subtask 1: 0 / 100