Submission #1085617

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1085617	2024-09-08T13:33:47 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	52 / 100	301 ms	28088 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) 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:33: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]
   33 |     for (long long i=0;i<v.size();i++) q.push_back({v[i],i+1});
      |                        ~^~~~~~~~~
jobs.cpp:36: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]
   36 |     for (long long i=0;i<q.size();i++)
      |                        ~^~~~~~~~~
jobs.cpp: In function 'bool moze(long long int)':
jobs.cpp:20:1: warning: control reaches end of non-void function [-Wreturn-type]
   20 | }
      | ^

Subtask #1

52.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	24 ms	3420 KB	Output isn't correct
2	Incorrect	23 ms	3420 KB	Output isn't correct
3	Incorrect	23 ms	3416 KB	Output isn't correct
4	Incorrect	24 ms	3420 KB	Output isn't correct
5	Incorrect	23 ms	3820 KB	Output isn't correct
6	Incorrect	24 ms	3420 KB	Output isn't correct
7	Incorrect	23 ms	3420 KB	Output isn't correct
8	Incorrect	24 ms	3588 KB	Output isn't correct
9	Correct	119 ms	3660 KB	Output is correct
10	Correct	118 ms	3660 KB	Output is correct
11	Correct	20 ms	3416 KB	Output is correct
12	Correct	40 ms	7000 KB	Output is correct
13	Correct	64 ms	11600 KB	Output is correct
14	Correct	93 ms	12648 KB	Output is correct
15	Incorrect	100 ms	15664 KB	Output isn't correct
16	Correct	136 ms	22592 KB	Output is correct
17	Correct	162 ms	24996 KB	Output is correct
18	Correct	171 ms	26148 KB	Output is correct
19	Partially correct	301 ms	28088 KB	Partially correct
20	Correct	163 ms	24400 KB	Output is correct