oj.uz

Submission #817643

# Submission time Handle Problem Language Result Execution time Memory
817643 2023-08-09T14:23:54 Z n3rm1n Job Scheduling (CEOI12_jobs) C++17
100 / 100
 216 ms 13884 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 1e6 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n, d, m;
vector < pair < int, int > > g;
void read()
{
    cin >> n >> d >> m;
    int x;
    for (int i = 1; i <= m; ++ i)
    {
        cin >> x;
        g.push_back({x, i});
    }
    sort(g.begin(), g.end());
}
bool check(int x)
{
    int i = 0, moment = 0;
    while (i < g.size())
    {
        moment ++;
        int j = i;
        if(g[j].first + d < moment)return false;
        while(j < g.size() && j - i + 1 <= x && g[j].first <= moment)
        {
            j ++;
        }
        i = j;
    }
    return (moment <= n);
}
int main()
{
    speed();

    read();
    int left = 1, right = m, mid, ans = m+1;
    while(left <= right)
    {
        mid = (left + right)/2;
        if(check(mid))
        {
            ans = mid;
            right = mid - 1;
        }
        else left = mid + 1;
    }
    cout << ans << endl;
    int i = 0, moment = 0;
    while (i < g.size())
    {
        moment ++;
        int j = i;
        while(j < g.size() && j - i + 1 <= ans && g[j].first <= moment)
        {
            cout << g[j].second << " ";
            j ++;
        }
        cout << 0 << endl;
        i = j;
    }
    while(moment < n)
    {
        cout << 0 << endl;
        moment ++;
    }
    return 0;
}

Compilation message

jobs.cpp: In function 'bool check(int)':
jobs.cpp:27:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     while (i < g.size())
      |            ~~^~~~~~~~~~
jobs.cpp:32:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         while(j < g.size() && j - i + 1 <= x && g[j].first <= moment)
      |               ~~^~~~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:58:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     while (i < g.size())
      |            ~~^~~~~~~~~~
jobs.cpp:62:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         while(j < g.size() && j - i + 1 <= ans && g[j].first <= moment)
      |               ~~^~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1764 KB Output is correct
2 Correct 18 ms 1760 KB Output is correct
3 Correct 14 ms 1872 KB Output is correct
4 Correct 25 ms 1772 KB Output is correct
5 Correct 14 ms 1852 KB Output is correct
6 Correct 14 ms 1872 KB Output is correct
7 Correct 26 ms 1872 KB Output is correct
8 Correct 14 ms 1764 KB Output is correct
9 Correct 25 ms 2000 KB Output is correct
10 Correct 39 ms 1904 KB Output is correct
11 Correct 21 ms 1744 KB Output is correct
12 Correct 48 ms 3200 KB Output is correct
13 Correct 79 ms 4684 KB Output is correct
14 Correct 89 ms 6224 KB Output is correct
15 Correct 104 ms 7696 KB Output is correct
16 Correct 134 ms 9248 KB Output is correct
17 Correct 180 ms 10668 KB Output is correct
18 Correct 177 ms 12188 KB Output is correct
19 Correct 216 ms 13884 KB Output is correct
20 Correct 174 ms 10672 KB Output is correct