Submission #655956

#	Time	Username	Problem	Language	Result	Execution time	Memory
655956		rarex	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	535 ms	20780 KiB

jobs

#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;
    }
    if(i % ans == 0)
        i = i / ans;
    else
        i = i / ans + 1;
    while(i <= m)
    {
        cout << 0 << endl;
        i++;
    }
    return 0;
}

• Subtask 1: 55 / 100