Submission #1109821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109821		MrPavlito	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	413 ms	27284 KiB

jobs

#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 (stderr)

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 / 100