oj.uz

Submission #743108

# Submission time Handle Problem Language Result Execution time Memory
743108 2023-05-17T08:09:11 Z Joo Job Scheduling (CEOI12_jobs) C++17
60 / 100
 1000 ms 16552 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();
        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
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 2800 KB Output is correct
2 Correct 205 ms 2860 KB Output is correct
3 Correct 214 ms 2804 KB Output is correct
4 Correct 218 ms 2804 KB Output is correct
5 Correct 229 ms 2804 KB Output is correct
6 Correct 276 ms 2816 KB Output is correct
7 Correct 246 ms 2888 KB Output is correct
8 Correct 255 ms 2800 KB Output is correct
9 Execution timed out 1078 ms 4228 KB Time limit exceeded
10 Execution timed out 1076 ms 4232 KB Time limit exceeded
11 Correct 135 ms 2620 KB Output is correct
12 Correct 245 ms 4852 KB Output is correct
13 Correct 397 ms 7636 KB Output is correct
14 Execution timed out 1075 ms 6432 KB Time limit exceeded
15 Correct 652 ms 12012 KB Output is correct
16 Execution timed out 1063 ms 10916 KB Time limit exceeded
17 Execution timed out 1051 ms 11100 KB Time limit exceeded
18 Execution timed out 1032 ms 13248 KB Time limit exceeded
19 Execution timed out 1060 ms 16552 KB Time limit exceeded
20 Execution timed out 1063 ms 11156 KB Time limit exceeded