Submission #1085619

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1085619	2024-09-08T13:38:44 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	92 / 100	280 ms	27940 KB

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 odg = bs(1,m);
    cout<<odg<<endl;
    pecati(odg);
    return 0;
}

Compilation message

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	3420 KB	Output is correct
2	Correct	24 ms	3420 KB	Output is correct
3	Correct	32 ms	3416 KB	Output is correct
4	Correct	23 ms	3420 KB	Output is correct
5	Correct	23 ms	3420 KB	Output is correct
6	Correct	23 ms	3420 KB	Output is correct
7	Correct	23 ms	3416 KB	Output is correct
8	Correct	23 ms	3420 KB	Output is correct
9	Correct	118 ms	3656 KB	Output is correct
10	Correct	131 ms	3584 KB	Output is correct
11	Correct	21 ms	4440 KB	Output is correct
12	Correct	41 ms	8024 KB	Output is correct
13	Correct	60 ms	13860 KB	Output is correct
14	Correct	92 ms	13876 KB	Output is correct
15	Incorrect	101 ms	16188 KB	Extra information in the output file
16	Correct	135 ms	22080 KB	Output is correct
17	Correct	155 ms	24244 KB	Output is correct
18	Correct	170 ms	25496 KB	Output is correct
19	Partially correct	280 ms	27940 KB	Partially correct
20	Correct	182 ms	24084 KB	Output is correct