Submission #1213859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213859		badge881	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	821 ms	20448 KiB

jobs

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

const int MAXN = 1e5 + 10;

vector<int> requests[MAXN], jobs[MAXN];

int n, d, m;

bool check(int x)
{

    priority_queue<pair<int, int>> q;

    for (int i = 1; i <= n; i++)
    {

        jobs[i].clear();

        for (auto j : requests[i])
            q.push({-i, j});

        int cnt = 0;

        while (cnt < x && !q.empty())
        {
            if (-q.top().first < i - d)
                return false;

            jobs[i].push_back(q.top().second);
            q.pop();

            cnt++;
        }
    }

    return true;
}

int main()
{
    scanf("%d %d %d", &n, &d, &m);

    for (int i = 1; i <= m; i++)
    {
        int d;
        scanf("%d", &d);
        requests[d].push_back(i);
    }

    int l = 1, r = m;

    while (l < r)
    {
        int mid = l + (r - l) / 2;

        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }

    check(r);
    printf("%d\n", r);

    for (int i = 1; i <= n; i++)
    {
        for (auto j : jobs[i])
            printf("%d ", j);
        printf("0\n");
    }

    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%d %d %d", &n, &d, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf("%d", &d);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 100 / 100