Submission #340200

#	Time	Username	Problem	Language	Result	Execution time	Memory
340200		blue	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	409 ms	17252 KiB

jobs

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

int N, D, M; //days, delay, jobs

struct job
{
    int i; //ind
    int d; //day
};

bool operator < (job A, job B)
{
    return A.d < B.d;
}

job J[1000000];

int b_search(int a, int b)
{
//    cout << a << ' ' << b << '\n';
    if(a == b) return a;

    int m = (a+b)/2;

    int done = 0; //number of jobs done

    for(int i = 1; i <= N; i++)
    {
        if(done < M && J[done].d + D < i)
        {
        //    cout << i << "too long" << '\n';
            return b_search(m+1, b);
        }
        for(int j = 0; j < m && done < M && J[done].d <= i; j++)
        {
            done++;
        }
    }
    if(done < M) return b_search(m+1, b);
    else return b_search(a, m);
}

int main()
{
    cin >> N >> D >> M;

    for(int i = 0; i < M; i++)
    {
        cin >> J[i].d;
        J[i].i = i+1;
    }
    sort(J, J+M);

    int m = b_search(1, M);

    int done = 0;

    cout << m << '\n';

    for(int i = 1; i <= N; i++)
    {
        for(int j = 0; j < m && done < M && J[done].d <= i; j++)
        {
            cout << J[done].i << ' ';
            done++;
        }
        cout << "0\n";
    }
}

• Subtask 1: 100 / 100