Submission #1085603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085603		vjudge1	Job Scheduling (CEOI12_jobs)	C++17	90 / 100	1036 ms	21240 KiB

jobs

#include <bits/stdc++.h>

using namespace std;
int n,d,m;
vector<int> v;

bool moze(int k)
{
    vector<int> q;
    q = v;
    sort(q.begin(),q.end());
    int den=1,koristeni=0;
    for (int i=0;i<q.size();i++)
    {
        if (koristeni==k)
        {
            koristeni=0;
            den++;
        }
        int x = q[i];

        if (den<x) den = x;
        if (x+d<den) return false;
        koristeni++;
    }
    return true;
}

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

void pecati(int k)
{
    vector<pair<int,int> > q;
    for (int i=0;i<v.size();i++) q.push_back({v[i],i+1});
    sort(q.begin(),q.end());
    int den=1,koristeni=0;
    for (int i=0;i<q.size();i++)
    {
        if (koristeni==k)
        {
            koristeni=0;
            den++;
            cout<<0<<endl;
        }
        int 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 (int i=0;i<m;i++)
    {
        int a;
        cin>>a;
        //freq[a]++;
        v.push_back(a);
    }

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

Compilation message (stderr)

jobs.cpp: In function 'bool moze(int)':
jobs.cpp:13:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (int i=0;i<q.size();i++)
      |                  ~^~~~~~~~~
jobs.cpp: In function 'void pecati(int)':
jobs.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i=0;i<v.size();i++) q.push_back({v[i],i+1});
      |                  ~^~~~~~~~~
jobs.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i=0;i<q.size();i++)
      |                  ~^~~~~~~~~

• Subtask 1: 90 / 100