Submission #333574

#	Time	Username	Problem	Language	Result	Execution time	Memory
333574		siddarthm	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	679 ms	13804 KiB

jobs

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

pair<int,int> orders[1000000];
int n,d,m;

bool works(int x)
{
    int point = 0;
    //cout << x << endl;
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<x; j++)
        {
            if(orders[point].first>i)
                break;
            if(i>(orders[point].first+d))
                return false;
            //cout << point << " ";
            point++;
            if(point==m)
                break;
        }
        //cout << endl;
        if(point==m)
            break;
    }
    if(point<m)
        return false;
    return true;
}

int main(){
    cin >> n >> d >> m;
    for(int i=0; i<m; i++)
    {
        cin >> orders[i].first;
        orders[i].second = i+1;
    }
    sort(orders, orders+m);
    int a = 1;
    int b = m;
    while(a!=b)
    {
        int mid = (a+b)/2;
        if(works(mid))
            b = mid;
        else
            a = mid+1;
        //cout << endl;
    }
    cout << a << endl;
    int point = 0;
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<a; j++)
        {
            if(point==m)
                break;
            if(orders[point].first>i)
                break;
            cout << orders[point].second << " ";
            point++;
        }
        cout << 0 << endl;
    }
}

• Subtask 1: 100 / 100