Submission #1300159

#TimeUsernameProblemLanguageResultExecution timeMemory
1300159hynmjJob Scheduling (CEOI12_jobs)C++20
0 / 100
321 ms33776 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
const long long N = 2e5 + 5;
int a[N];
int n, d, m;
vector<int> fr[N];
vector<int> ans[N];
int f(int k, stack<int> q)
{
    for (int day = n; q.size() && day >= 0; day--)
    {
        for (int i = 0; i < k && q.size(); i++)
        {
            // cout << day << ' ' << q.top() << endl;
            if (q.top() < day - d)
                break;
            else if (q.top() >= day - d and q.top() <= day)
            {
                // ans[day].push_back(fr[q.top()].back());
                // fr[q.top()].pop_back();
                q.pop();
            }
            else
                break;
        }
    }
    return q.size() == 0;
}
void print(int k, stack<int> q)
{
    for (int day = n; q.size() && day >= 0; day--)
    {
        for (int i = 0; i < k && q.size(); i++)
        {
            // cout << day << ' ' << q.top() << endl;
            if (q.top() < day - d)
                break;
            else if (q.top() >= day - d and q.top() <= day)
            {
                ans[day].push_back(fr[q.top()].back());
                fr[q.top()].pop_back();
                q.pop();
            }
            else
                break;
        }
    }
}
void solve()
{
    cin >> n >> d >> m;
    int e;
    for (int i = 1; i <= m; i++)
    {
        cin >> e;
        fr[e].push_back(i);
    }
    stack<int> q;
    for (int i = 1; i <= n; i++)
    {
        for (auto j : fr[i])
            q.push(i);
    }
    int l = 0, r = m + 1;
    while (r - l > 1)
    {
        int mid = (r + l) / 2;
        f(mid, q) ? (r = mid) : (l = mid);
    }
    print(r, q);
    // cout << r << endl;
    for (int i = 1; i <= n; i++)
    {
        for (auto j : ans[i])
        {
            cout << j << ' ';
        }
        cout << 0 << endl;
    }
}

signed main()
{
    // ios_base::sync_with_stdio(0);
    // cin.tie(NULL);
    // cout.tie(NULL);
    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++)
    {
        // cout << "Case #" << i << ':' << ' ';
        solve();
        // cout << endl;
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...