Submission #497307

#	Time	Username	Problem	Language	Result	Execution time	Memory
497307		Sharky	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	357 ms	21996 KiB

jobs

#include <bits/stdc++.h>
// --------------------
#define sharky using namespace
#define fai std
#define wrong ios_base::sync_with_stdio(0);
#define answer cin.tie(0);
// --------------------
sharky fai;

#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#define sz(x) (ll) (x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define endl "\n"
#define vll vector<ll>
#define pl pair<ll, ll>
const int inf = 1e9 + 5;
const int MOD = 1e9 + 7;
#define FOR(i, a, b) for (ll i = a; i < (b); i++)
#define F0R(i, a) for (ll i = 0; i < (a); i++)
bool cmp(pl x, pl y) { return x.fi < y.fi; }
ll n, d, m; vector<pl> v;
bool check(ll x) {
    ll idx = 1;
    for (ll i = 1; i <= n; i++) {
        for (ll j = 0; j < x; j++) {
            if (v[idx].fi > i) break;
            if (v[idx].fi + d >= i) idx++;
            else return false;
            if (idx == m + 1) return true; 
        }
    }
    return false;
}
int main() {
    wrong answer
    cin >> n >> d >> m; v.resize(m + 5);
    for (ll i = 1; i <= m; i++) cin >> v[i].fi, v[i].se = i;
    sort(v.begin() + 1, v.begin() + m + 1, cmp);
    ll l = 1, r = m, mid = (l + r) / 2, ans = 0;
    while (l < r) {
        mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    cout << l << endl; 
    ll idx = 1;
    for (ll i = 1; i <= n; i++) {
        for (ll j = 0; j < l; j++) {
            if (v[idx].fi > i) break;
            if (v[idx].fi + d >= i) cout << v[idx].se << " ", idx++;
        }
        cout << "0\n";
    }
    return 0;
}
/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4 
*/

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:44:41: warning: unused variable 'ans' [-Wunused-variable]
   44 |     ll l = 1, r = m, mid = (l + r) / 2, ans = 0;
      |                                         ^~~

• Subtask 1: 100 / 100