Submission #474267

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
474267	2021-09-17T17:04:01 Z	satyam_G	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	335 ms	13700 KB

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

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	1612 KB	Output is correct
2	Correct	27 ms	1628 KB	Output is correct
3	Correct	27 ms	1624 KB	Output is correct
4	Correct	27 ms	1628 KB	Output is correct
5	Correct	27 ms	1600 KB	Output is correct
6	Correct	27 ms	1616 KB	Output is correct
7	Correct	30 ms	1624 KB	Output is correct
8	Correct	34 ms	1696 KB	Output is correct
9	Correct	42 ms	1856 KB	Output is correct
10	Correct	42 ms	1856 KB	Output is correct
11	Correct	40 ms	1672 KB	Output is correct
12	Correct	69 ms	3168 KB	Output is correct
13	Correct	103 ms	4588 KB	Output is correct
14	Correct	161 ms	6140 KB	Output is correct
15	Correct	171 ms	7544 KB	Output is correct
16	Correct	251 ms	9108 KB	Output is correct
17	Correct	254 ms	10544 KB	Output is correct
18	Correct	289 ms	12100 KB	Output is correct
19	Correct	335 ms	13700 KB	Output is correct
20	Correct	255 ms	10608 KB	Output is correct