Submission #474267

#	Time	Username	Problem	Language	Result	Execution time	Memory
474267		satyam_G	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	335 ms	13700 KiB

jobs

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

#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define mp make_pair
#define fi first
#define se second
#define repi(n) for (int i = 0; i < n; i++)
#define repj(n) for (int j = 0; j < n; j++)
#define cout_vec(a) for(auto q : a) cout << q << " "; cout << "\n"
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL)
#define t_cases int t; cin >> t; while(t--)
#define debug(a) cout << a << "\n"

using intl = long long;
using vi = vector<int>;
using vd = vector<double>;
using vil = vector<intl>;
using pi = pair<int, int>;
using pil = pair<intl, intl>;
using vpi = vector<pair<int, int>>;
using vpil = vector<pair<intl, intl>>;

const intl MOD = 1000000007;
const intl MAXL = 50000;

bool is_pos(vector<pair<int, int>> &a, int n, int d, int nm) {

    int i = 0, j = 0, day;

    for (day = 1; day <= n; day++) {

        while (j < a.size() and j - i + 1 <= nm and a[j].fi <= day) {
            j++;
        }

        while (i < j) {
            if (day - a[i].fi > d) return false;
            i++;
        }

    }

    if (i < n) return false;

    return true;

}


void solve() {

    int n, d, m; cin >> n >> d >> m;
    vector<pair<int, int>> a(m);
    repi(m) {
        cin >> a[i].fi;
        a[i].se = i;
    }

    sort(a.begin(), a.end());

    int s = 1, e = 1000000000, ans = -1;

    while (s <= e) {

        int mid = s + (e - s) / 2;

        if (is_pos(a, n, d, mid)) {
            ans = mid;
            e = mid - 1;
        } else {
            s = mid + 1;
        }
    }

    cout << ans << "\n";

    int i = 0, j = 0, day;

    for (day = 1; day <= n; day++) {

        while (j < a.size() and j - i + 1 <= ans and a[j].fi <= day) {
            j++;
        }

        while (i < j) {
            cout << a[i].se + 1 << " ";
            i++;
        }

        cout << "0\n";

    }



}

int main() {

    FAST;

//#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//#endif

    // freopen("socdist.in", "r", stdin);
    // freopen("socdist.out", "w", stdout);

    // t_cases solve();
    solve();

}

Compilation message (stderr)

jobs.cpp: In function 'bool is_pos(std::vector<std::pair<int, int> >&, int, int, int)':
jobs.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         while (j < a.size() and j - i + 1 <= nm and a[j].fi <= day) {
      |                ~~^~~~~~~~~~
jobs.cpp: In function 'void solve()':
jobs.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         while (j < a.size() and j - i + 1 <= ans and a[j].fi <= day) {
      |                ~~^~~~~~~~~~

• Subtask 1: 100 / 100