Submission #558163

#	Time	Username	Problem	Language	Result	Execution time	Memory
558163		hibiki	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	195 ms	20484 KiB

jobs

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

#define pb push_back

int n,d,m;
int work[1000005];
vector<int> day[100005];

int main()
{
    scanf("%d %d %d",&n,&d,&m);
    for(int i = 1; i <= m; i++)
    {
        scanf("%d",&work[i]);
        day[work[i]].pb(i);
    }

    int l = 1, r = m;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        bool ok = true, ans = false;
        queue<int> unfin;

        if(l==r)
        {
            ans = true;
            printf("%d\n",mid);
        }

        for(int i = 1; i <= n; i++)
        {
            // printf("day %d: ",i);
            if(!unfin.empty() && work[unfin.front()] + d < i)
            {
                ok = false;
                break;
            }

            int done = 0;
            while(done < mid && !unfin.empty())
            {
                if(ans) printf("%d ",unfin.front());

                done++;
                unfin.pop();
            }

            for(int j: day[i])
            {
                if(done < mid)
                {
                    if(ans) printf("%d ",j);

                    done++;
                }
                else
                    unfin.push(j);
            }

            if(ans) printf("0\n");
        }

        if(l==r) break;

        if(!unfin.empty()) ok = false;

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

    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100