Submission #540454

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
540454	2022-03-20T11:22:33 Z	BhavayGoyal	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	503 ms	26452 KB

jobs

#include <bits/stdc++.h>
using namespace std;

#define vii vector<vector<int>>
#define pii pair<int, int>
#define f first
#define s second
int inf = 1e9;

int n, d, m; 

pair<bool, vii> isFiss(int mid, vector<pii> &arr)
{
    int idx = 0;
    vii answer(n);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < mid; j++)
        {
            if (arr[idx].f > i) break;
            if (i <= arr[idx].f + d) answer[i-1].push_back(arr[idx++].s);
            else return {false, answer};
            if (idx == m) return {true, answer};
        }
    }
    return {false, answer};
}

void sol()
{
    cin >> n >> d >> m;
    vector<pii> arr(m);
    for (int i = 0; i < m; i++)
    {
        cin >> arr[i].f;
        arr[i].s = i+1;
    }
    sort (arr.begin(), arr.end());

    int i = 1, j = m;
    int ans = m;
    vii actualans;
    while (i <= j)
    {
        int mid = (i+j)/2;
        auto f = isFiss(mid, arr);
        if (f.f)
        {
            actualans = f.s;
            ans = mid;
            j = mid-1;
        }
        else i = mid+1;
    }
    cout << ans << endl;
    for (int i = 0; i < n; i++)
    {
        for (auto j : actualans[i]) cout << j << " ";
        cout << 0 << endl;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++)
        sol();
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	2968 KB	Output is correct
2	Correct	41 ms	3004 KB	Output is correct
3	Correct	41 ms	3000 KB	Output is correct
4	Correct	42 ms	3084 KB	Output is correct
5	Correct	41 ms	2968 KB	Output is correct
6	Correct	44 ms	3020 KB	Output is correct
7	Correct	49 ms	2976 KB	Output is correct
8	Correct	41 ms	3076 KB	Output is correct
9	Correct	189 ms	9672 KB	Output is correct
10	Correct	184 ms	9708 KB	Output is correct
11	Correct	39 ms	2752 KB	Output is correct
12	Correct	78 ms	4984 KB	Output is correct
13	Correct	108 ms	8576 KB	Output is correct
14	Correct	190 ms	10792 KB	Output is correct
15	Correct	188 ms	10920 KB	Output is correct
16	Correct	271 ms	15760 KB	Output is correct
17	Correct	345 ms	18844 KB	Output is correct
18	Correct	358 ms	18256 KB	Output is correct
19	Correct	503 ms	26452 KB	Output is correct
20	Correct	323 ms	18900 KB	Output is correct