Submission #1308700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308700		j_a_i_kumar	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	103 ms	19916 KiB

jobs

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define vv vector
#define pb push_back
#define ff first
#define ss second
#define ll long long
#define setbits(x) (__builtin_popcountll(x))
#define getUnique(x) sort((x).begin(), (x).end()), (x).erase(unique((x).begin(), (x).end()), (x).end())

template <typename T>
using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// *st.find_by_order(i) - i-th element; st.order_of_key(val) - count < val; for multiset : use less<pair<T, int>>
template <typename T>
using maxHeap = priority_queue<T>;
template <typename T>
using minHeap = priority_queue<T, vector<T>, greater<T>>;

const int mod = 1e9 + 7;
const long long inf = 1e18;

vector<pair<int, int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};                                        // grid
vector<pair<int, int>> dir2 = {{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}}; // knight

// lower_bound(arr.begin(), arr.end(), k,[](const pair<int, int>& arrEle, int val) {return arrEle.second < val;});
// upper_bound(arr.begin(), arr.end(), k,[](int val, const pair<int, int>& arrEle) {return val < arrEle.second;});
// sort(arr.begin(), arr.end(),[](const vector<int>& x, const vector<int>& y) {return x[2] < y[2];});
// auto fun = [&](auto &&self, int u, int p)-> void {self(self, v, u)}; // lambda-dfs

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); // for random inputs
// int pivot = a[l + RNG() % (r - l + 1)]; // for fast quick-sort
struct my_hash
{
    static uint64_t splitmix64(uint64_t x)
    {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
// unordered_map<long long, int, my_hash> safe_map;
// gp_hash_table<long long, int, my_hash> safe_htable; // gnu pbds

void solve()
{
    int n, d, m;
    cin >> n >> d >> m;
    vv<int> job[n + 1];
    for (int i = 1; i <= m; i++)
    {
        int x;
        cin >> x;
        job[x].pb(i);
    }

    auto pred = [&](int x) -> bool
    {
        int cnt = 0;
        int j = 1;
        for (int i = 1; i <= n - d; i++)
        {
            int k = 0;
            if (j < i)
                j = i, cnt = 0;
            while (k < job[i].size() && j <= n && j <= i + d)
            {
                cnt++;
                k++;
                if (cnt == x)
                    cnt = 0, j++;
            }
            if (k < job[i].size())
                return 0;
        }
        return 1;
    };

    int low = 1, high = m;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (pred(mid))
            high = mid - 1;
        else
            low = mid + 1;
    }

    vector<int> ans[n + 1];
    int j = 1;
    for (int i = 1; i <= n - d; i++)
    {
        int k = 0;
        j = max(j, i);
        while (k < job[i].size() && j <= n && j <= i + d)
        {
            ans[j].pb(job[i][k++]);
            if (ans[j].size() == low)
                j++;
        }
    }

    cout << low << endl;
    for (int i = 1; i <= n; i++)
    {
        for (auto &j : ans[i])
            cout << j << " ";
        cout << "0\n";
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);

    int t = 1;
    // cin >> t;
    // cin.ignore();

    while (t-- > 0)
    {
        solve();
    }

    return 0;
}

• Subtask 1: 100 / 100