Submission #706271

#	Time	Username	Problem	Language	Result	Execution time	Memory
706271		ToroTN	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	894 ms	15372 KiB

jobs

#include<bits/stdc++.h>
using namespace std;
#define X first 
#define Y second
#define pb push_back
int n,d,m,job[100005],num,st,md,ed,type,flag;
priority_queue<int> pq;
priority_queue<pair<int,int> >pq2;
vector<int> v[100005];
int main()
{
    scanf("%d%d%d",&n,&d,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&num),++job[num];
        v[num].pb(i);
    }
    st=1;
    ed=1000000000;
    while(ed>=st)
    {
        md=(st+ed)/2;
        //printf("%d %d %d\n",st,md,ed);
        type=0;
        while(!pq.empty())pq.pop();
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<job[i];j++)pq.push(-i);
            if(pq.size()!=0)
            {
                if(i>-pq.top()+d)
                {
                    type=-1;
                }
                flag=min((int)pq.size(),md);
                for(int j=1;j<=flag;j++)pq.pop();
            }
        }
        if(pq.size()>0)type=-1;
        if(type==0)
        {
            ed=md-1;
        }else
        {
            st=md+1;
        }
    }
    while(!pq.empty())
    {
        pq.pop();
    }
    printf("%d\n",st);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<v[i].size();j++)
        {
            pq2.push({-i,v[i][j]});
        }
        if(pq2.size()!=0)
        {
            flag=min((int)pq2.size(),st);
            for(int j=1;j<=flag;j++)
            {
                printf("%d ",pq2.top().Y);
                pq2.pop();
            }
        }
        printf("0\n");
    }
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(int j=0;j<v[i].size();j++)
      |                     ~^~~~~~~~~~~~
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",&num),++job[num];
      |         ~~~~~^~~~~~~~~~~

• Subtask 1: 100 / 100