Submission #655975

#	Time	Username	Problem	Language	Result	Execution time	Memory
655975		rarex	Job Scheduling (CEOI12_jobs)	C++14	30 / 100	473 ms	20776 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 b)
{
    long long ok = 1, i, k;
    for(i=1; i<=n; i++)
        if(i > (v[i].x + d - 1) * b)
            ok = 0;
    k = n / b;
    if(n % b != 0)
        k++;
    if(k > m)
        return 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 = 1;
    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: 30 / 100