oj.uz

Submission #340200

# Submission time Handle Problem Language Result Execution time Memory
340200 2020-12-27T09:22:07 Z blue Job Scheduling (CEOI12_jobs) C++11
100 / 100
 409 ms 17252 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2028 KB Output is correct
2 Correct 36 ms 2028 KB Output is correct
3 Correct 37 ms 2028 KB Output is correct
4 Correct 36 ms 2056 KB Output is correct
5 Correct 36 ms 2028 KB Output is correct
6 Correct 36 ms 2028 KB Output is correct
7 Correct 38 ms 2156 KB Output is correct
8 Correct 36 ms 2028 KB Output is correct
9 Correct 42 ms 2156 KB Output is correct
10 Correct 42 ms 2304 KB Output is correct
11 Correct 44 ms 2156 KB Output is correct
12 Correct 107 ms 3948 KB Output is correct
13 Correct 133 ms 5868 KB Output is correct
14 Correct 196 ms 8044 KB Output is correct
15 Correct 226 ms 9580 KB Output is correct
16 Correct 301 ms 12268 KB Output is correct
17 Correct 347 ms 13932 KB Output is correct
18 Correct 356 ms 15212 KB Output is correct
19 Correct 409 ms 17252 KB Output is correct
20 Correct 343 ms 13932 KB Output is correct