oj.uz

Submission #743115

# Submission time Handle Problem Language Result Execution time Memory
743115 2023-05-17T08:11:16 Z Joo Job Scheduling (CEOI12_jobs) C++17
70 / 100
 1000 ms 16428 KB 
#include <bits/stdc++.h>
using namespace std;

int n, D, M;
vector<pair<int, int>> vec;
vector<vector<int>> ansDetail;

bool chk(int mid)
{
    int ptr = 0;
    for (int day = 1; day <= n; day++)
    {
        ansDetail[day].clear();
        if (ptr >= M)
            continue;
        for (int i = 1; i <= mid; i++)
        {
            if (ptr < M and day > vec[ptr].first + D)
                return false;

            if (ptr < M and day >= vec[ptr].first)
            {
                ansDetail[day].emplace_back(vec[ptr].second);
                ptr++;
            }
        }
    }
    return true;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> D >> M;
    ansDetail.resize(n + 1);
    for (int i = 1; i <= M; i++)
    {
        int x;
        cin >> x;
        vec.emplace_back(x, i);
    }

    sort(vec.begin(), vec.end());

    int l = 1, r = M, ans = -1;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (chk(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }

    cout << ans << "\n";
    for (int i = 1; i <= n; i++)
    {
        for (int v : ansDetail[i])
        {
            cout << v << " ";
        }
        cout << "0\n";
    }
}

Subtask #1
70.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2520 KB Output is correct
2 Correct 39 ms 2504 KB Output is correct
3 Correct 52 ms 2644 KB Output is correct
4 Correct 55 ms 2512 KB Output is correct
5 Correct 70 ms 2508 KB Output is correct
6 Correct 79 ms 2504 KB Output is correct
7 Correct 79 ms 2500 KB Output is correct
8 Correct 91 ms 2508 KB Output is correct
9 Correct 36 ms 4768 KB Output is correct
10 Correct 37 ms 4932 KB Output is correct
11 Correct 129 ms 2172 KB Output is correct
12 Correct 277 ms 4132 KB Output is correct
13 Correct 409 ms 6664 KB Output is correct
14 Execution timed out 1083 ms 4944 KB Time limit exceeded
15 Correct 656 ms 10544 KB Output is correct
16 Execution timed out 1080 ms 8896 KB Time limit exceeded
17 Execution timed out 1080 ms 8896 KB Time limit exceeded
18 Execution timed out 1072 ms 16428 KB Time limit exceeded
19 Execution timed out 1082 ms 13780 KB Time limit exceeded
20 Execution timed out 1082 ms 8908 KB Time limit exceeded