Submission #1226840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226840		marselel	Job Scheduling (CEOI12_jobs)	C++20	60 / 100	835 ms	13488 KiB

jobs

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


using ll = long long;
using ld = long double;

# define all(a) a.begin(), a.end()
# define rall(a) a.rbegin(), a.rend()
# define pii pair<int, int>
# define pll pair<ll, ll>
#ifdef LOCAL
#include "algo/debug.h"
#else
# define debug(x)
#endif
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 2e15;
const ld RANDMAX = (1LL << 32) - 1;
const ll mod = 998'244'353;


/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int n, d, m;

const int maxn = 100'010;
vector<int> a[maxn];
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////



bool check(int mid) {
    multiset<int> mlt;
    for (int i = 1; i <= n; ++i) {
        for (auto v : a[i]) {
            mlt.insert(i);
        }
        for (int j = 0; j < mid; ++j) {
            if (mlt.empty())break;
            auto v = *mlt.begin();
            if (v + d < i) {
                return false;
            }
            mlt.erase(mlt.begin());
        }
    }
    return true;
}

void solve() {
    cin >> n >> d >> m;
    for (int i = 0; i < m; ++i) {
        int v; cin >> v;
        a[v].push_back(i);
    }
    int l = 0, r = n;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    cout << r << '\n';
    multiset<pii> mlt;
    for (int i = 1; i <= n; ++i) {
        for (auto v : a[i]) {
            mlt.insert({i, v});
        }
        for (int j = 0; j < r; ++j) {
            if (mlt.empty())break;
            auto [day, ind] = *mlt.begin();
            cout << ind + 1 << ' ';
            mlt.erase(mlt.begin());
        }
        cout << 0 << '\n';
    }
}












signed main() {
#ifdef LOCAL
    (void)!freopen("input.txt", "r", stdin);
#else
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
#endif
    int tt = 1;
    //cin >> tt;
/*  Бисмил ляяхи ррахмаани ррахиим.
    Изаа джаа’э насрул лаахи валь фатх.
    Ва ра’этэ нааса ядхулююнэ фии дии нил ляяхи афвааджа.
    Фа саббих би хамди раббикя вастагфирхь.
    Иннаху кяяна тавваабэ

    Бисмил ляяхи ррахмаани ррахиим.
    Куль а‘уузу би раббин наас.
    Мааликин наас.
    Иляяхин наас.
    Мин шарриль васваасиль ханнаас.
    Аллязии ювасвису фии судуурин наас. Миналь джиннати ван наас

    Бисмил ляяхи ррахмаани ррахиим.
    Куль яяайюхэль кяяфируун. 
    Ляя а‘буду маа та‘будуун. 
    Ва ляя энтум ‘аабиду унэ маа а‘буд. 
    Ва ляя ана ‘аабидум маа ‘абадтум. Ва ляя энтум ‘аабидуунэ маа а‘буд. 
    Лякум диинукум ва лияд диин 
*/
    while (tt--) {
        solve();
        cout << '\n';
    }
    cerr << "\nRuntime = " << ((ld)clock() / CLOCKS_PER_SEC) << " ms\n";
}

• Subtask 1: 60 / 100