Submission #478504

#	Time	Username	Problem	Language	Result	Execution time	Memory
478504		FluffyGhost8	Job Scheduling (CEOI12_jobs)	C++17	75 / 100	1096 ms	16804 KiB

jobs

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <array>
#include <fstream>
#include <cmath>
#include <string>
#include <numeric>
#include <tuple>
#include <unordered_map>
#include <queue>
#include <unordered_set>
using namespace std;
#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define pb push_back

bool works(ll mid);
ll n, d, m;
ll low = 1;
ll high = m;
vector<pll> v;
ll input;
int main()
{
    cin >> n >> d >> m;
    high = m;
    for(int i = 0; i < m; i++)
    {
        cin >> input;
        v.pb(mp(input-1, input+d-1));
    }
    sort(v.begin(), v.end());
    ll ans;
    //cout << "hello" << " " << low << " " << high << endl;
    while(low <= high)
    {
        ll mid = low+(high-low)/2;
        //cout << mid << " " << works(mid) << endl;
        if(works(mid))
        {
            ans = mid;
            high = mid-1;
        } else {
            low = mid+1;
        }
    }
    cout << ans << endl;
    for(int i = 0; i < n; i++)
    {
        cout << 0 << endl;
    }
}

bool works(ll mid)
{
    int pos = 0;
    int pschng;
    //cout << endl << endl << mid << endl << endl;
    for(int i = 0; i < n; i++)
    {
        pschng = 0;
        for(int j = pos; j < (pos+mid); j++)
        {
            if(j >= v.size())
            {
                break;
            }
            if(v[j].second < i)
            {
                return false;
            }
            if(v[j].first <= i)
            {
                pschng++;
            }
            //cout << i << " " << j << " " << v[j].first << " " << v[j].second << " " << pos << endl;
        }
        pos += pschng;
    }
    return true;
}

Compilation message (stderr)

jobs.cpp: In function 'bool works(long long int)':
jobs.cpp:69:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             if(j >= v.size())
      |                ~~^~~~~~~~~~~

• Subtask 1: 75 / 100