oj.uz

Submission #1109821

# Submission time Handle Problem Language Result Execution time Memory
1109821 2024-11-07T17:20:21 Z MrPavlito Job Scheduling (CEOI12_jobs) C++17
100 / 100
 413 ms 27284 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define pii pair<int,int>

using namespace std;

const int MAXN = 1e5+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;
int n,d,m;
vector<pii> niz;
vector<pii> resenje;

bool check(int mid)
{
    vector<int> kopija(m);
    for(int i=0; i<m; i++)kopija[i] = niz[i].fi;
    int cnt = 0;
    int trd = niz[0].fi;
    for(int i=0; i<m; i++)
    {
        if(cnt >= mid)
        {
            cnt = 0;
            trd++;
        }
        if(kopija[i] > trd)
        {
            trd = kopija[i];
            cnt = 0;
        }
        else
        {
            cnt++;
            if(trd - kopija[i] > d)return false;
        }
        kopija[i] = trd;
    }
    for(int i=0; i<m; i++)resenje[i].fi = kopija[i];
    for(int i=0; i<m; i++)resenje[i].sc = niz[i].sc;
    return true;
}


signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--)
    {
        cin >> n >> d >> m;
        niz.resize(m);
        resenje.resize(m);
        for(int i=0; i<m; i++)cin >> niz[i].fi, niz[i].sc = i;
        sort(all(niz));
        int l = 1;
        int r = m;
        int rez = m;
        while(l<=r)
        {
            int mid = l + r>>1;
            if(check(mid))
            {
                r = mid-1;
                rez = mid;
            }
            else l = mid+1;
        }
        cout << rez << endl;
        sort(all(resenje));
        vector<vector<int>> mat(n+1);
        for(int i=0; i<resenje.size(); i++)
        {
            mat[resenje[i].fi].pb(resenje[i].sc);
        }
        for(int i=1; i<=n; i++)
        {
            if(!mat[i].size())
            {
                cout << 0 << endl;
                continue;
            }
            for(auto x: mat[i])cout << x+1 << " ";
            cout << 0 << endl;
        }
    }
}

/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:66:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |             int mid = l + r>>1;
      |                       ~~^~~
jobs.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for(int i=0; i<resenje.size(); i++)
      |                      ~^~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3528 KB Output is correct
2 Correct 36 ms 3460 KB Output is correct
3 Correct 33 ms 3520 KB Output is correct
4 Correct 33 ms 3528 KB Output is correct
5 Correct 33 ms 3528 KB Output is correct
6 Correct 32 ms 3272 KB Output is correct
7 Correct 33 ms 3520 KB Output is correct
8 Correct 32 ms 3272 KB Output is correct
9 Correct 162 ms 5604 KB Output is correct
10 Correct 162 ms 5652 KB Output is correct
11 Correct 28 ms 2924 KB Output is correct
12 Correct 55 ms 5688 KB Output is correct
13 Correct 96 ms 9096 KB Output is correct
14 Correct 121 ms 12328 KB Output is correct
15 Correct 132 ms 13488 KB Output is correct
16 Correct 178 ms 16716 KB Output is correct
17 Correct 208 ms 21476 KB Output is correct
18 Correct 240 ms 22796 KB Output is correct
19 Correct 413 ms 27284 KB Output is correct
20 Correct 216 ms 21484 KB Output is correct