Submission #677191

#	Time	Username	Problem	Language	Result	Execution time	Memory
677191		sofija6	Job Scheduling (CEOI12_jobs)	C++14	75 / 100	528 ms	56060 KiB

jobs

#include <bits/stdc++.h>
#define ll long long
#define MAXM 1000010
using namespace std;
ll n,d,m;
pair<ll,ll> a[MAXM];
bool Check(ll x)
{
    vector<pair<ll,ll> > v[x+2];
    ll cur=1;
    for (ll i=1;i<=m;i++)
    {
        v[cur].push_back(a[i]);
        cur++;
        if (cur>x)
            cur=1;
    }
    for (ll i=1;i<=x;i++)
    {
        cur=1;
        for (ll j=0;j<v[i].size();j++)
        {
            if (cur<v[i][j].first)
                cur=v[i][j].first;
            if (cur-v[i][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+d+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 'bool Check(long long int)':
jobs.cpp:21:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for (ll j=0;j<v[i].size();j++)
      |                     ~^~~~~~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:68:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for (ll j=0;j<v[i].size();j++)
      |                     ~^~~~~~~~~~~~
jobs.cpp:78:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for (ll j=0;j<days[i].size();j++)
      |                     ~^~~~~~~~~~~~~~~
jobs.cpp:65:18: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |     for (ll i=1;i<=ans;i++)
      |                 ~^~~~~

• Subtask 1: 75 / 100