Submission #1082215

# Submission time Handle Problem Language Result Execution time Memory
1082215 2024-08-30T20:54:30 Z galaxy_kitty Job Scheduling (CEOI12_jobs) C++17
100 / 100
240 ms 17492 KB
#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

int main()
{
    int n, d, m;
    cin >> n >> d >> m;
    int day[100000] = {};
    vector<int> arr[n];
    for (int i = 0; i < m; i++)
    {
        int a;
        cin >> a;
        day[a - 1]++;
        arr[a - 1].push_back(i + 1);
    }
    int l = 0, r = m, mid = (l + r + 1) / 2;
    while (l < r)
    {
        set<pair<int, int>> q;
        bool f = true;
        for (int i = 0; i < n; i++)
        {
            if (day[i] != 0)
            {
                q.insert({i, day[i]});
            }
            int a = mid;
            while (a > 0 && q.begin() != q.end())
            {
                int b = min(a, (*q.begin()).second);
                q.insert({(*q.begin()).first, (*q.begin()).second - b});
                q.erase(++q.begin());
                a -= b;
                if ((*q.begin()).second == 0)
                {
                    q.erase(q.begin());
                }
            }
            if (q.begin() != q.end() && i - (*q.begin()).first == d)
            {
                f = false;
                break;
            }
        }
        if (f)
        {
            r = mid - 1;
            mid = (l + r + 1) / 2;
        }
        else
        {
            l = mid;
            mid = (l + r + 1) / 2;
        }
    }
    mid++;
    cout << mid << "\n";
    set<pair<int, int>> q;
    for (int i = 0; i < n; i++)
    {
        for (auto a : arr[i])
        {
            q.insert({i, a});
        }
        for (int a = 0; (a < mid && q.begin() != q.end()); a++)
        {
            cout << (*q.begin()).second << " ";
            q.erase(q.begin());
        }
        cout << 0 << "\n";
    }
}
# Verdict Execution time Memory Grader output
1 Correct 31 ms 6860 KB Output is correct
2 Correct 31 ms 6860 KB Output is correct
3 Correct 32 ms 6824 KB Output is correct
4 Correct 31 ms 6856 KB Output is correct
5 Correct 32 ms 7040 KB Output is correct
6 Correct 32 ms 6856 KB Output is correct
7 Correct 33 ms 6976 KB Output is correct
8 Correct 31 ms 6868 KB Output is correct
9 Correct 32 ms 5204 KB Output is correct
10 Correct 38 ms 5200 KB Output is correct
11 Correct 26 ms 2384 KB Output is correct
12 Correct 55 ms 4688 KB Output is correct
13 Correct 77 ms 5972 KB Output is correct
14 Correct 143 ms 9908 KB Output is correct
15 Correct 121 ms 9044 KB Output is correct
16 Correct 169 ms 11860 KB Output is correct
17 Correct 216 ms 14156 KB Output is correct
18 Correct 204 ms 14164 KB Output is correct
19 Correct 240 ms 17492 KB Output is correct
20 Correct 207 ms 14160 KB Output is correct