oj.uz

Submission #478504

# Submission time Handle Problem Language Result Execution time Memory
478504 2021-10-07T19:35:17 Z FluffyGhost8 Job Scheduling (CEOI12_jobs) C++17
75 / 100
 1000 ms 16804 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 2368 KB Output is correct
2 Correct 56 ms 2368 KB Output is correct
3 Correct 65 ms 2368 KB Output is correct
4 Correct 73 ms 2464 KB Output is correct
5 Correct 92 ms 2588 KB Output is correct
6 Correct 97 ms 2368 KB Output is correct
7 Correct 96 ms 2360 KB Output is correct
8 Correct 108 ms 2368 KB Output is correct
9 Correct 198 ms 2368 KB Output is correct
10 Correct 154 ms 2368 KB Output is correct
11 Correct 112 ms 2368 KB Output is correct
12 Correct 219 ms 4408 KB Output is correct
13 Correct 348 ms 8656 KB Output is correct
14 Execution timed out 1087 ms 8612 KB Time limit exceeded
15 Correct 580 ms 8584 KB Output is correct
16 Execution timed out 1088 ms 16736 KB Time limit exceeded
17 Execution timed out 1096 ms 16796 KB Time limit exceeded
18 Correct 973 ms 16796 KB Output is correct
19 Execution timed out 1064 ms 16804 KB Time limit exceeded
20 Execution timed out 1088 ms 16792 KB Time limit exceeded