Submission #1361954

#TimeUsernameProblemLanguageResultExecution timeMemory
1361954h.oussamaJob Scheduling (CEOI12_jobs)C++20
30 / 100
63 ms17220 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int mod = 1e9 + 7;//998244353

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int N,M,D;
    cin>>N>>D>>M;
    vector<int>J(N+1);
    vector<vector<int>>P(N+1);
    for (int i = 0; i < M; i++)
    {
        int x;
        cin>>x;
        J[x]++;
        P[x].push_back(i+1);
    }
    int lo=1;int hi=M;
    int mid;
    int ans=0;
    while (lo<=hi)
    {
        mid = lo+(hi-lo)/2;
        bool ok=true;
        queue<int>cur;
        for (int i = 1; i <= N; i++)
        {
            cur.push(J[i]);
            int val=mid;
            while (val>0 && !cur.empty())
            {
                int nuh=cur.front();
                int meow=max(0,nuh-val);
                val=max(0,val-nuh);
                cur.pop();
                if(meow)cur.push(meow);
            }
        }
        if(cur.size()>D)ok=false;
        if(ok && cur.empty()){
            ans=mid;
            hi=mid-1;
        }else{
            lo=mid+1;
        }
    }
    cout<<ans;
    queue<int>what;
    for (int i = 1; i <= N; i++)
    {
        cout<<"\n";
        for (auto sd:P[i])
        {
            what.push(sd);
        }
        for (int i = 0; i < ans && !what.empty(); i++)
        {
            cout<<what.front()<<" ";
            what.pop();
        }
        cout<<0;
    }
    
    
    return 0;

}
#Result Execution timeMemoryGrader output
Fetching results...