제출 #944396

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
944396		slumio	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	330 ms	25268 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ull = unsigned long long;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
/*I liked you once but not anymore now*/

bool sea(int n, int m, int d, vector<pair<int, int>> q, int mid)
{

    for (int i = 1; i <= n; i++)
    {
        int cnt = mid;
        while (!q.empty() && --cnt >=0)
        {
            if (i-q.back().first>=0&&i-q.back().first <= d)
                q.pop_back();
            else
                break;
        }
    }

    return q.empty();
}

void printans(int n, int m, int d, vector<pair<int, int>> q, int mid)
{  
    
    for (int i = 1; i <= n; i++)
    {
        int cnt = mid;
        while (!q.empty() && --cnt>=0)
        {
            if (i-q.back().first>=0&&i-q.back().first <= d)
               { cout<<q.back().second<<" ";q.pop_back();}
            else
                break;
        }
        cout<<0<<endl;
    }

    
}
void solve()
{
    int n, d, m;
    cin >> n >> d >> m;

    vector<pair<int, int>> a;
    for (int i = 1; i <= m; i++)
    {
        int pp;
        cin >> pp;
        a.push_back(pair(pp, i));
    }

    sort(a.begin(), a.end(), [&](const pair<int, int> &aa, const pair<int, int> &bb)
         {
             if (aa.first != bb.first)
                 return aa.first > bb.first;
             else
                 return bb.second < aa.second;
         });

         //for(auto &[x,y]:a)cout<<x<<" "<<y<<endl;

    int ans = 1e8;
    int low = 1;
    int high = 1e7, mid;
    for (int i = 0; i <30 && low <= high; i++)
    {
        if (low <= high)
        {
            mid = (high + low) / 2;
            if (sea(n, m, d, a, mid))
            {
                ans = min(mid, ans);
                high = mid;
            }
            else
                low = mid;
        }
    }

    cout << ans << endl;
    printans(n, m, d, a,ans);

    return;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    solve();
    return 0;
}

• Subtask 1: 100 / 100