Submission #71517

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
71517	2018-08-25T01:07:20 Z	MathStudent2002	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	457 ms	16396 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	43 ms	1784 KB	Output is correct
2	Correct	38 ms	1784 KB	Output is correct
3	Correct	43 ms	1984 KB	Output is correct
4	Correct	39 ms	1984 KB	Output is correct
5	Correct	37 ms	1984 KB	Output is correct
6	Correct	43 ms	2024 KB	Output is correct
7	Correct	38 ms	2024 KB	Output is correct
8	Correct	38 ms	2024 KB	Output is correct
9	Correct	177 ms	2296 KB	Output is correct
10	Correct	182 ms	2296 KB	Output is correct
11	Correct	36 ms	2296 KB	Output is correct
12	Correct	72 ms	3484 KB	Output is correct
13	Correct	100 ms	4892 KB	Output is correct
14	Correct	151 ms	6428 KB	Output is correct
15	Correct	184 ms	7852 KB	Output is correct
16	Correct	251 ms	9388 KB	Output is correct
17	Correct	255 ms	10904 KB	Output is correct
18	Correct	291 ms	12332 KB	Output is correct
19	Correct	457 ms	16396 KB	Output is correct
20	Correct	251 ms	16396 KB	Output is correct