Submission #677194

#	Time	Username	Problem	Language	Result	Execution time	Memory
677194		sofija6	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	304 ms	27320 KiB

jobs

#include <bits/stdc++.h>
#define ll int
#define MAXM 1000002
using namespace std;
ll n,d,m;
pair<ll,ll> a[MAXM];
bool Check(ll x)
{
    for (ll i=1;i<=x;i++)
    {
        ll cur=1;
        for (ll j=1;j<=m;j+=x)
        {
            if (cur<a[j].first)
                cur=a[j].first;
            if (cur-a[j].first>d)
                return false;
            cur++;
        }
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> d >> m;
    for (ll i=1;i<=m;i++)
    {
        cin >> a[i].first;
        a[i].second=i;
    }
    sort(a+1,a+1+m);
    ll l=1,r=m,mid,ans;
    while (l<=r)
    {
        mid=(l+r)/2;
        if (Check(mid))
        {
            ans=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    cout << ans << "\n";
    vector<pair<ll,ll> > v[ans+2];
    vector<ll> days[n+2];
    ll cur=1;
    for (ll i=1;i<=m;i++)
    {
        v[cur].push_back(a[i]);
        cur++;
        if (cur>ans)
            cur=1;
    }
    for (ll i=1;i<=ans;i++)
    {
        cur=1;
        for (ll j=0;j<v[i].size();j++)
        {
            if (cur<v[i][j].first)
                cur=v[i][j].first;
            days[cur].push_back(v[i][j].second);
            cur++;
        }
    }
    for (ll i=1;i<=n;i++)
    {
        for (ll j=0;j<days[i].size();j++)
            cout << days[i][j] << " ";
        cout << 0 << "\n";
    }
    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for (ll j=0;j<v[i].size();j++)
      |                     ~^~~~~~~~~~~~
jobs.cpp:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for (ll j=0;j<days[i].size();j++)
      |                     ~^~~~~~~~~~~~~~~
jobs.cpp:33:20: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   33 |     ll l=1,r=m,mid,ans;
      |                    ^~~

• Subtask 1: 100 / 100