Submission #71517

#	Time	Username	Problem	Language	Result	Execution time	Memory
71517		MathStudent2002	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	457 ms	16396 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].y = i+1;
    }
    
    sort(job,job+M);
}
 
bool test(long long mech)
{
    int d = 1;
    int num = 0;
    
    for(int i = 0; i < M;i++)
    {
        if(d > (job[i].x+D))
            return false;
            
        while(job[i].x > d)
        {
            d++;
            num = 0;
        }
        num++;
        if(num == mech)
        {
            d++;
            num = 0;
        }
    }
    return true;
}
 
void print(long long mech)
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout << mech << endl;
    int d = 1;
    int num = 0;
    
    for(int i = 0; i < M;i++)
    {
        while(job[i].x > d)
        {
            d++;
            num = 0;
            cout << 0 << endl;
        }
        cout << job[i].y << " ";
        num++;
        if(num == mech)
        {
            d++;
            num = 0;
            cout << 0 << endl;
        }
    }
    
    while(d <= N)
    {
        cout << 0 << endl;
        d++;
    }
}
 
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: 100 / 100