Submission #1109733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109733		MrPavlito	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	525 ms	36920 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 = 2e5+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;
int n,d,m;
vector<pii> niz;
vector<pii> kopija;
vector<pii> resenje;

bool check(int mid)
{
    kopija = niz;
    int cnt = 0;
    int trd = niz[0].fi;
    for(int i=0; i<m; i++)
    {
        if(cnt >= mid)
        {
            cnt = 0;
            trd++;
        }
        if(kopija[i].fi > trd)
        {
            trd = kopija[i].fi;
            cnt = 0;
        }
        else
        {
            cnt++;
            if(trd - kopija[i].fi > d)return false;
        }
        kopija[i].fi = trd;
    }
    resenje = kopija;
    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);
        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(MAXN);
        for(int i=0; i<resenje.size(); i++)
        {
            mat[resenje[i].fi].pb(resenje[i].sc);
        }
        for(int i=0; i<MAXN; i++)
        {
            if(!mat[i].size())
            {
                cout << 0 << endl;
                continue;
            }
            for(auto x: mat[i])cout << x << " ";
            cout << 0 << endl;
        }
    }
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:64:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |             int mid = l + r>>1;
      |                       ~~^~~
jobs.cpp:75: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]
   75 |         for(int i=0; i<resenje.size(); i++)
      |                      ~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 100