Submission #987276

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
987276	2024-05-22T13:38:16 Z	aykhn	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	289 ms	21720 KB

jobs

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define inf 0x3F3F3F3F
 
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, d, m;
    cin >> n >> d >> m;
    vector<int> v[n + 1];
    for (int i = 1; i <= m; i++)
    {
        int x;
        cin >> x;
        v[x].push_back(i);
    }
    int l = 1, r = m;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        queue<array<int, 2>> q;
        int ok = 1;
        for (int i = 1; i <= n; i++)
        {
            for (int x : v[i]) q.push({x, i});
            int k = mid;
            while (!q.empty() && k--) q.pop();
            if (!q.empty() && q.front()[1] + d == i)
            {
                ok = 0;
                break;
            }
        }
        ok &= q.empty();
        if (ok) r = mid;
        else l = mid + 1;
    }
    cout << l << '\n';
    queue<array<int, 2>> q;
    for (int i = 1; i <= n; i++)
    {
        for (int x : v[i]) q.push({x, i});
        int k = l;
        while (!q.empty() && k--) 
        {
            cout << q.front()[0] << ' ';
            q.pop();
        }
        cout << 0 << '\n';
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	3788 KB	Output is correct
2	Correct	35 ms	3852 KB	Output is correct
3	Correct	35 ms	4036 KB	Output is correct
4	Correct	43 ms	4044 KB	Output is correct
5	Correct	36 ms	4028 KB	Output is correct
6	Correct	35 ms	4056 KB	Output is correct
7	Correct	34 ms	4048 KB	Output is correct
8	Correct	35 ms	4048 KB	Output is correct
9	Correct	35 ms	4956 KB	Output is correct
10	Correct	36 ms	5084 KB	Output is correct
11	Correct	28 ms	2384 KB	Output is correct
12	Correct	59 ms	4748 KB	Output is correct
13	Correct	88 ms	8012 KB	Output is correct
14	Correct	134 ms	11184 KB	Output is correct
15	Correct	145 ms	11772 KB	Output is correct
16	Correct	178 ms	15320 KB	Output is correct
17	Correct	219 ms	18708 KB	Output is correct
18	Correct	253 ms	18004 KB	Output is correct
19	Correct	289 ms	21720 KB	Output is correct
20	Correct	226 ms	18960 KB	Output is correct