Submission #1085595

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1085595	2024-09-08T13:09:52 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	70 / 100	1000 ms	11956 KB

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()
{
    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: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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	2380 KB	Output is correct
2	Correct	63 ms	2312 KB	Output is correct
3	Correct	65 ms	2208 KB	Output is correct
4	Correct	78 ms	2364 KB	Output is correct
5	Correct	63 ms	2332 KB	Output is correct
6	Correct	64 ms	2284 KB	Output is correct
7	Correct	65 ms	2328 KB	Output is correct
8	Correct	65 ms	2360 KB	Output is correct
9	Correct	231 ms	2512 KB	Output is correct
10	Correct	239 ms	2436 KB	Output is correct
11	Correct	198 ms	2332 KB	Output is correct
12	Correct	445 ms	5292 KB	Output is correct
13	Correct	671 ms	8404 KB	Output is correct
14	Correct	928 ms	9796 KB	Output is correct
15	Execution timed out	1053 ms	6396 KB	Time limit exceeded
16	Execution timed out	1044 ms	10376 KB	Time limit exceeded
17	Execution timed out	1055 ms	11508 KB	Time limit exceeded
18	Execution timed out	1077 ms	11448 KB	Time limit exceeded
19	Execution timed out	1065 ms	11600 KB	Time limit exceeded
20	Execution timed out	1018 ms	11956 KB	Time limit exceeded