oj.uz

Submission #709906

# Submission time Handle Problem Language Result Execution time Memory
709906 2023-03-14T19:06:37 Z groshi Job Scheduling (CEOI12_jobs) C++17
100 / 100
 357 ms 17208 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
vector<pair<int,int> > Q;
int n,d,m;
void wypisz(int x)
{
    cout<<x<<"\n";
    queue<pair<int,int> > kolejka;
    bool git=1;
    int gdzie=0;
    for(int i=1;i<=n;i++)
    {
        while(gdzie<Q.size() && Q[gdzie].first==i)
        {
            kolejka.push(Q[gdzie]);
            gdzie++;
        }
        for(int j=1;j<=x;j++)
        {
            if(kolejka.size()==0)
                break;
            int kiedy=kolejka.front().first;
            cout<<kolejka.front().second<<" ";
            kolejka.pop();
        }
        cout<<"0\n";
    }
}
bool git(int x)
{
    queue<pair<int,int> > kolejka;
    bool git=1;
    int gdzie=0;
    for(int i=1;i<=n;i++)
    {
        while(gdzie<Q.size() && Q[gdzie].first==i)
        {
            kolejka.push(Q[gdzie]);
            gdzie++;
        }
        for(int j=1;j<=x;j++)
        {
            if(kolejka.size()==0)
                break;
            int kiedy=kolejka.front().first;
            if(kiedy+d<i)
            {
                git=0;
                break;
            }
            kolejka.pop();
        }
        if(git==0)
            break;
    }
    if(git && kolejka.size()==0)
        return 1;
    else return 0;
}
int32_t main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int x;
    cin>>n>>d>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x;
        Q.push_back({x,i});
    }
    sort(Q.begin(),Q.end());
    int pocz=1,kon=m+1,sre,ostd;
    while(pocz<kon)
    {
        sre=(pocz+kon)/2;
        if(git(sre))
        {
            ostd=sre;
            kon=sre;
        }
        else pocz=sre+1;
    }
    wypisz(ostd);
    return 0;
}

Compilation message

jobs.cpp: In function 'void wypisz(int)':
jobs.cpp:16:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         while(gdzie<Q.size() && Q[gdzie].first==i)
      |               ~~~~~^~~~~~~~~
jobs.cpp:25:17: warning: unused variable 'kiedy' [-Wunused-variable]
   25 |             int kiedy=kolejka.front().first;
      |                 ^~~~~
jobs.cpp:12:10: warning: unused variable 'git' [-Wunused-variable]
   12 |     bool git=1;
      |          ^~~
jobs.cpp: In function 'bool git(int)':
jobs.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         while(gdzie<Q.size() && Q[gdzie].first==i)
      |               ~~~~~^~~~~~~~~
jobs.cpp: In function 'int32_t main()':
jobs.cpp:87:11: warning: 'ostd' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |     wypisz(ostd);
      |     ~~~~~~^~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2760 KB Output is correct
2 Correct 31 ms 2752 KB Output is correct
3 Correct 27 ms 2756 KB Output is correct
4 Correct 27 ms 2748 KB Output is correct
5 Correct 27 ms 2760 KB Output is correct
6 Correct 27 ms 2740 KB Output is correct
7 Correct 27 ms 2744 KB Output is correct
8 Correct 35 ms 2760 KB Output is correct
9 Correct 41 ms 2244 KB Output is correct
10 Correct 39 ms 2264 KB Output is correct
11 Correct 33 ms 2144 KB Output is correct
12 Correct 72 ms 4044 KB Output is correct
13 Correct 103 ms 5936 KB Output is correct
14 Correct 143 ms 8320 KB Output is correct
15 Correct 189 ms 9588 KB Output is correct
16 Correct 205 ms 11948 KB Output is correct
17 Correct 236 ms 13992 KB Output is correct
18 Correct 288 ms 15016 KB Output is correct
19 Correct 357 ms 17208 KB Output is correct
20 Correct 249 ms 13880 KB Output is correct