Submission #655951

#TimeUsernameProblemLanguageResultExecution timeMemory
655951rarexJob Scheduling (CEOI12_jobs)C++14
55 / 100
434 ms20836 KiB
#include <iostream>
#include <algorithm>
using namespace std;

const int nmax = 1e6 + 7;

long long n, m, d;

struct nr
{
    long long x;
    long long poz;
}v[nmax];

bool cmp(nr a, nr b)
{
    return a.x < b.x;
}

long long solve(long long m)
{
    long long ok = 1, i;
    for(i=1; i<=n; i++)
        if(i > (v[i].x + d) * m)
            ok = 0;
    return ok;
}

int main()
{
    long long i,st,dr,ans = -1;
    cin >> m >> d >> n;
    for(i=1; i<=n; i++)
    {
        cin >> v[i].x;
        v[i].poz = i;
    }
    sort(v+1,v+1+n,cmp);
    st = 0;
    dr = n;
    while(st <= dr)
    {
        long long mij = (st + dr) / 2;
        if(solve(mij) == 1)
        {
            ans = mij;
            dr = mij - 1;
        }
        else
            st = mij + 1;
    }
    cout << ans << endl;
    for(i=1;i<=n;i++)
    {
        cout << v[i].poz << " ";
        if(i % ans == 0)
            cout << 0 <<endl;
    }
    i = i / ans + 1;
    while(i <= m)
    {
        cout << 0 << endl;
        i++;
    }
    return 0;
}

#Verdict Execution timeMemoryGrader output
Fetching results...