Submission #304881

#	Time	Username	Problem	Language	Result	Execution time	Memory
304881		waterfall	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	942 ms	31264 KiB

jobs

#include<bits/stdc++.h>
using namespace std;

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)

vector<int> v[100005];
int n, m, d;

bool works(int num, pair<int, int> requests[])
{
    int curDay = 1;
    for(int i = 0; i < m; i++)
    {
        curDay = max (curDay, requests[i].first);
        while(v[curDay].size() >= num)
        {
            curDay++;
            if(curDay > n)
            {
                return false;
            }
        }

        if(curDay > n || curDay - requests[i].first > d)
        {
            return false;
        }
        else
        {
            v[curDay].push_back(requests[i].second);
        }
    }
    return true;
}

int32_t main()
{
    cin >> n >> d >> m;

    pair<int, int> requests[m];
    for(int i = 0; i < m; i++)
    {
        cin >> requests[i].first;
        requests[i].second = i + 1;
    }

    sort(requests, requests + m);

    int lower = 1;
    int upper = m;
    int ans = m;
    while(lower < upper)
    {
        int mid = (lower + upper ) / 2;
        if(works(mid, requests))
        {
            upper = mid;
            ans = mid;
        }
        else
        {
            lower = mid + 1;
        }

        for(int i = 1; i <= n; i++)
        {
            v[i].clear();
        }
    }

    cout << ans << endl;

    works(ans, requests);

    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j < v[i].size(); j++)
        {
            cout << v[i][j] << " ";
        }
        cout << 0 << endl;
    }
    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'bool works(long long int, std::pair<long long int, long long int>*)':
jobs.cpp:31:32: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   31 |         while(v[curDay].size() >= num)
      |               ~~~~~~~~~~~~~~~~~^~~~~~
jobs.cpp: In function 'int32_t main()':
jobs.cpp:93:26: 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]
   93 |         for(int j = 0; j < v[i].size(); j++)
      |                        ~~^~~~~~~~~~~~~

• Subtask 1: 100 / 100