Submission #1085620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085620		vjudge1	Job Scheduling (CEOI12_jobs)	C++17	92 / 100	285 ms	28188 KiB

jobs

#include <bits/stdc++.h>

using namespace std;
long long n,d,m;
vector<long long> v;
long long freq[100001];

bool moze(long long k)
{
    long long rabota = 0;
    for (long long i=1;i<=n;i++)
    {
        rabota += freq[i];
        long long potrebni_denovi = rabota/k;
        if (rabota%k>0) potrebni_denovi++;
        if (potrebni_denovi>d+1) return false;
        rabota-=k;
        if (rabota<0) rabota = 0;
    }
    if (rabota<=0) return true;
}

long long bs(long long l,long long r)
{
    if (l==r) return l;
    long long mid = (l+r)/2;
    if (moze(mid)) return bs(l,mid);
    else return bs(mid+1,r);
}

void pecati(long long k)
{
    vector<pair<long long,long long> > q;
    for (long long i=0;i<v.size();i++) q.push_back({v[i],i+1});
    sort(q.begin(),q.end());
    long long den=1,koristeni=0;
    for (long long i=0;i<q.size();i++)
    {
        if (koristeni==k)
        {
            koristeni=0;
            den++;
            cout<<0<<endl;
        }
        long long x = q[i].first,it=q[i].second;

        if (den<x)
        {
            while(den<x)
            {
                den++;
                cout<<0<<endl;
            }
        }
        koristeni++;
        cout<<it<<" ";
    }
    while(den<=n)
    {
        cout<<0<<endl;
        den++;
    }

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>d>>m;
    for (long long i=0;i<m;i++)
    {
        long long a;
        cin>>a;
        freq[a]++;
        v.push_back(a);
    }

    long long kec = 1;
    long long odg = bs(kec,m);
    cout<<odg<<endl;
    pecati(odg);
    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'void pecati(long long int)':
jobs.cpp:34:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (long long i=0;i<v.size();i++) q.push_back({v[i],i+1});
      |                        ~^~~~~~~~~
jobs.cpp:37:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (long long i=0;i<q.size();i++)
      |                        ~^~~~~~~~~
jobs.cpp: In function 'bool moze(long long int)':
jobs.cpp:21:1: warning: control reaches end of non-void function [-Wreturn-type]
   21 | }
      | ^

• Subtask 1: 92 / 100