Submission #1085596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085596		vjudge1	Job Scheduling (CEOI12_jobs)	C++17	70 / 100	1075 ms	12488 KiB

jobs

#include <bits/stdc++.h>

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

bool moze(int k)
{
    priority_queue<int> q;
    for (int i=0;i<v.size();i++) q.push(-v[i]);
    int den=1,koristeni=0;
    while(!q.empty())
    {
        if (koristeni==k)
        {
            koristeni=0;
            den++;
        }
        int x = -q.top();
        q.pop();

        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)
{
    priority_queue<pair<int,int> > q;
    for (int i=0;i<v.size();i++) q.push({-v[i],i+1});
    int den=1,koristeni=0;
    while(!q.empty())
    {
        if (koristeni==k)
        {
            koristeni=0;
            den++;
            cout<<0<<endl;
        }
        int x = -q.top().first,it=q.top().second;
        q.pop();

        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:11:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for (int i=0;i<v.size();i++) q.push(-v[i]);
      |                  ~^~~~~~~~~
jobs.cpp: In function 'void pecati(int)':
jobs.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i=0;i<v.size();i++) q.push({-v[i],i+1});
      |                  ~^~~~~~~~~

• Subtask 1: 70 / 100