제출 #655949

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
655949		rarex	Job Scheduling (CEOI12_jobs)	C++14	40 / 100	1086 ms	17192 KiB

jobs

#include <iostream>
#include <algorithm>
using namespace std;

const int nmax = 1e6 + 7;

int n, m, d;

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

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

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

int main()
{
    int 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)
    {
        int 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;
}

• Subtask 1: 40 / 100