Submission #1085596

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1085596	2024-09-08T13:10:47 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	70 / 100	1000 ms	12488 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()
{
    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: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	58 ms	2264 KB	Output is correct
2	Correct	57 ms	2400 KB	Output is correct
3	Correct	57 ms	2384 KB	Output is correct
4	Correct	59 ms	2384 KB	Output is correct
5	Correct	57 ms	2400 KB	Output is correct
6	Correct	62 ms	2400 KB	Output is correct
7	Correct	61 ms	2372 KB	Output is correct
8	Correct	61 ms	2268 KB	Output is correct
9	Correct	226 ms	2456 KB	Output is correct
10	Correct	237 ms	2440 KB	Output is correct
11	Correct	187 ms	2380 KB	Output is correct
12	Correct	438 ms	4204 KB	Output is correct
13	Correct	651 ms	8412 KB	Output is correct
14	Correct	907 ms	8520 KB	Output is correct
15	Execution timed out	1070 ms	9944 KB	Time limit exceeded
16	Execution timed out	1043 ms	12488 KB	Time limit exceeded
17	Execution timed out	1022 ms	11144 KB	Time limit exceeded
18	Execution timed out	1063 ms	11936 KB	Time limit exceeded
19	Execution timed out	1046 ms	11608 KB	Time limit exceeded
20	Execution timed out	1075 ms	10568 KB	Time limit exceeded