oj.uz

Submission #899646

# Submission time Handle Problem Language Result Execution time Memory
899646 2024-01-06T17:44:44 Z ivaziva Job Scheduling (CEOI12_jobs) C++14
100 / 100
 340 ms 28200 KB 
#include <bits/stdc++.h>

using namespace std;

long long n,d,m;
vector<pair<pair<long long,long long>,long long>> vec;

bool check(long long mid)
{
    long long dan=1;
    bool da=true;
    long long poz=0;
    while (dan<=n)
    {
        if (!da) break;
        long long br=1;
        while (br<=mid and poz<vec.size())
        {
            long long pocetak=vec[poz].first.first;
            long long kraj=vec[poz].first.second;
            if (dan>=pocetak and dan<=kraj) {poz++;br++;}
            else if (dan>kraj) {da=false;break;}
            else if (dan<pocetak) break;
        }
        dan++;
    }
    return da;
}

void resenje(long long rez)
{
    long long dan=1;
    long long poz=0;
    while (dan<=n)
    {
        long long br=1;
        while (br<=rez and poz<vec.size())
        {
            long long pocetak=vec[poz].first.first;
            long long kraj=vec[poz].first.second;
            if (dan>=pocetak and dan<=kraj)
            {
                cout<<vec[poz].second<<" ";
                poz++;br++;
            }
            else if (dan<pocetak) break;
        }
        cout<<0<<endl;dan++;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>d>>m;
    for (long long i=1;i<=m;i++)
    {
        long long x; cin>>x;
        vec.push_back({{x,x+d},i});
    }
    sort(vec.begin(),vec.end());
    long long l=1;
    long long r=m;
    long long rez=-1;
    while (l<=r)
    {
        long long mid=(l+r)/2;
        if (check(mid)) {rez=mid;r=mid-1;}
        else l=mid+1;
    }
    cout<<rez<<endl;
    resenje(rez);
}

Compilation message

jobs.cpp: In function 'bool check(long long int)':
jobs.cpp:17:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         while (br<=mid and poz<vec.size())
      |                            ~~~^~~~~~~~~~~
jobs.cpp: In function 'void resenje(long long int)':
jobs.cpp:37:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         while (br<=rez and poz<vec.size())
      |                            ~~~^~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4300 KB Output is correct
2 Correct 28 ms 3536 KB Output is correct
3 Correct 28 ms 3536 KB Output is correct
4 Correct 28 ms 3536 KB Output is correct
5 Correct 27 ms 5068 KB Output is correct
6 Correct 28 ms 4048 KB Output is correct
7 Correct 27 ms 4044 KB Output is correct
8 Correct 28 ms 3532 KB Output is correct
9 Correct 131 ms 3532 KB Output is correct
10 Correct 130 ms 3788 KB Output is correct
11 Correct 26 ms 4560 KB Output is correct
12 Correct 51 ms 7424 KB Output is correct
13 Correct 70 ms 14024 KB Output is correct
14 Correct 105 ms 13740 KB Output is correct
15 Correct 117 ms 15528 KB Output is correct
16 Correct 155 ms 27152 KB Output is correct
17 Correct 187 ms 26020 KB Output is correct
18 Correct 209 ms 26796 KB Output is correct
19 Correct 340 ms 28200 KB Output is correct
20 Correct 197 ms 26036 KB Output is correct