Apartments

#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <iterator>
#include <limits>
#include <set>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

template <typename T>
std::ostream &operator<<(std::ostream &os, const vector<T> &obj) {
    bool first = true;
    for (const auto &o : obj) {
        if (first) {
            cout << o;
            first = false;
        } else {
            cout << ' ' << o;
        }
    }
    cout << endl;
    return os;
}

std::ostream &operator<<(std::ostream &os, const vector<pair<int, int>> &obj) {
    for (const auto &o : obj) {
        cout << o.first << ' ' << o.second << endl;
    }
    cout << endl;
    return os;
}

// {adjacent, adjacents_idx(self), weight}
vector<vector<tuple<int, int, int>>> adjacency;
set<int> seen;
int source, drain;

bool _ff_dfs(int node, int minimum, vector<tuple<int, int, int> *> &out) {
    seen.insert(node);
    // cout << "dfs(" << node << ')' << endl;
    for (auto &adj : adjacency[node]) {
        auto &[nb, rev, w] = adj;
        // cout << "nb: " << nb << endl;
        if (w <= minimum) {
            continue;
        }
        if (seen.contains(nb)) {
            continue;
        }
        if (nb == drain || _ff_dfs(nb, minimum, out)) {
            out.push_back(&adj);
            // cout << "<" << endl;
            return true;
        }
        // cout << "<" << endl;
    }
    return false;
}

float max_flow(int init_threshhold) {
    float total = 0;
    vector<tuple<int, int, int> *> path_adj;
    while (init_threshhold > 0) {
        while (_ff_dfs(source, init_threshhold - 1, path_adj)) {
            // cout << "dfs ran" << endl;
            int minimum = numeric_limits<int>::max();
            for (const auto ptr : path_adj) {
                int w = get<2>(*ptr);
                minimum = min(w, minimum);
            }
            // cout << "minimum: " << minimum << endl;
            for (auto ptr : path_adj) {
                auto &[nb, rev, w] = *ptr;
                auto &rev_w = get<2>(adjacency[nb][rev]);
                w -= minimum;
                rev_w += minimum;
            }
            total += minimum;
            // cout << "total: " << total << endl;
            path_adj.clear();
            seen.clear();
        }
        init_threshhold >>= 1;
    }
    return total;
}

int matchings(int left, int right, const vector<pair<int, int>> &edges) {
    adjacency = vector<vector<tuple<int, int, int>>>(
        left + right + 2, vector<tuple<int, int, int>>(0));
    source = left + right;
    drain = left + right + 1;

    auto edge = [&](int a, int b) {
        int rev_fwd = adjacency[b].size();
        int rev_back = adjacency[a].size();
        adjacency[a].push_back({b, rev_fwd, 1});
        adjacency[b].push_back({a, rev_back, 0});
    };
    for (int i = 0; i < left; ++i) {
        edge(source, i);
    }
    for (int i = 0; i < right; ++i) {
        edge(left + i, drain);
    }
    for (const auto &e : edges) {
        edge(e.first, e.second + left);
    }
    return max_flow(left + right);
}

int main(int argc, char **argv) {
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> desired_size(n);
    vector<int> sizes(m);
    for (int i = 0; i < n; ++i)
        cin >> desired_size[i];
    for (int i = 0; i < m; ++i)
        cin >> sizes[i];

    sort(sizes.begin(), sizes.end());
    vector<pair<int, int>> edges;
    for (int i = 0; i < n; ++i) {
        int des = desired_size[i];

        auto lo = lower_bound(sizes.begin(), sizes.end(), des - k);
        auto hi = upper_bound(sizes.begin(), sizes.end(), des + k);
        for (; lo < hi; ++lo) {
            edges.push_back({i, distance(sizes.begin(), lo)});
        }
    }
    cout << matchings(n, m, edges) << endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: RUNTIME ERROR

Test 6

Verdict: RUNTIME ERROR

Test 7

Verdict: RUNTIME ERROR

Test 8

Verdict: RUNTIME ERROR

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: TIME LIMIT EXCEEDED

Test 14

Verdict: TIME LIMIT EXCEEDED

Test 15

Verdict: TIME LIMIT EXCEEDED

Test 16

Verdict: TIME LIMIT EXCEEDED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED