Submission #71485

#	Time	Username	Problem	Language	Result	Execution time	Memory
71485		MathStudent2002	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	707 ms	14028 KiB

jobs

//wait darn

#include<bits/stdc++.h>

using namespace std;

#define MAXM 1000005
#define x first 
#define y second

int M, N, D;

pair<int,int> job[MAXM];

void read()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cin >> N >> D >> M;
    for(int i = 0; i < M; i++)
    {
        cin >> job[i].x;
        job[i].x += D;
        job[i].y = i+1;
    }
    
    sort(job,job+M);
}

bool test(long long mech)
{
    if(mech < (M+N)/N)
    {
        if(mech*N < M)
            return false;
    }
    
    for(int i = 0; i < M;i++)
    {
        if(job[i].x < ((i/mech)+1))
            return false;
    }
    return true;
}

void print(long long mech)
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout << mech << endl;
    int d = 0;
    for(int i = 0; i < M;i++)
    {
        cout << job[i].y << " ";
        
        if((i+1)%mech == 0)
        {
            cout << 0 << endl;
            d++;
        }
    }
    
    for(; d < N; d++)
        cout << 0 << endl;
}

int solve()
{
    int lo = 1, hi = M, mi;
    while(hi - lo > 1)
    {
        mi = (lo+hi)/2;
        if(test(mi))
            hi = mi;
        else
            lo = mi;
    }
    if(test(lo))
        return lo;
    return hi;
}

int main()
{
    read();
    print(solve());
}

• Subtask 1: 55 / 100