Submission #1085603

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1085603	2024-09-08T13:15:48 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	90 / 100	1000 ms	21240 KB

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

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	2532 KB	Output is correct
2	Correct	44 ms	2632 KB	Output is correct
3	Correct	40 ms	2632 KB	Output is correct
4	Correct	42 ms	2624 KB	Output is correct
5	Correct	45 ms	2708 KB	Output is correct
6	Correct	54 ms	2628 KB	Output is correct
7	Correct	39 ms	2632 KB	Output is correct
8	Correct	41 ms	2640 KB	Output is correct
9	Correct	156 ms	2760 KB	Output is correct
10	Correct	168 ms	2776 KB	Output is correct
11	Correct	91 ms	2524 KB	Output is correct
12	Correct	214 ms	5100 KB	Output is correct
13	Correct	288 ms	7916 KB	Output is correct
14	Correct	480 ms	9836 KB	Output is correct
15	Incorrect	541 ms	11544 KB	Output isn't correct
16	Correct	761 ms	17172 KB	Output is correct
17	Correct	879 ms	18952 KB	Output is correct
18	Correct	848 ms	19840 KB	Output is correct
19	Execution timed out	1036 ms	21240 KB	Time limit exceeded
20	Correct	892 ms	18724 KB	Output is correct