Submission #522321

#TimeUsernameProblemLanguageResultExecution timeMemory
522321MOUF_MAHMALATJob Scheduling (CEOI12_jobs)C++14
100 / 100
240 ms17176 KiB
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
#define F first
#define S second
using namespace std;
typedef int ll;
ll n,d,m,x;
pair<ll,ll>a[1000009];
inline bool can(ll op)
{
    ll r=0,i=1;
    while(r<m)
    {
        ll o=0;
        while(r<m&&a[r].F<=i&&o<op)
        {
            if(a[r].F+d<i)
                return 0;
            r++,o++;
        }
        i++;
    }
    return 1;
}
void go(ll op)
{
    ll r=0,i=1;
    while(r<m)
    {
        ll o=0;
        while(r<m&&a[r].F<=i&&o<op)
        {
            cout<<a[r].S<<" ";
            r++,o++;
        }
        cout<<0<<"\n";
        i++;
    }
    while(i<=n){
        cout<<0<<"\n";
        i++;
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>d>>m;
    for(ll i=0;i<m;i++)
    {
         cin>>a[i].F;
         a[i].S=i+1;
    }
    sort(a,a+m);
    ll l=0,r=m,mid;
    while(r-l>1)
    {
        mid=(l+r)/2;
        if(can(mid))
            r=mid;
        else
            l=mid;
    }
    cout<<r<<"\n";
    go(r);
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...