Apartments

#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <iterator>
#include <set>
#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;
}

vector<vector<int>> dir_edges;

struct FordFulkerson {
    vector<vector<pair<int, float>>> edges;
    int source;
    int drain;
    set<int> visited;

    FordFulkerson(vector<vector<pair<int, float>>> edges, int source, int drain)
        : edges{edges}, source(source), drain(drain), visited() {}

    void debug() {
        cout << '{';
        for (auto x : visited) {
            cout << x << ',';
        }
        cout << '}' << endl;
    }

    bool dfs(int node, vector<float *> &out) {
        visited.insert(node);
        // cout << "dfs(" << node << ')' << endl;
        for (auto &[nb, w] : edges[node]) {
            // cout << "nb: " << nb << endl;
            // if (w <= 0 || visited.contains(nb))
            //     continue;
            // debug();
            if (w <= 0) {
                // cout << "zero w" << endl;
                continue;
            }
            if (visited.contains(nb)) {
                // cout << "visited" << endl;
                continue;
            }

            if (nb == drain) {
                out.push_back(&w);
                // cout << "found drain" << endl;
                return true;
            }

            // cout << ">" << endl;
            if (dfs(nb, out)) {
                out.push_back(&w);
                return true;
            }
            // cout << "<" << endl;
        }
        return false;
    }

    float solve() {
        float total = 0;
        vector<float *> path_weights;
        visited.clear();
        while (dfs(source, path_weights)) {
            // cout << "dfs ran" << endl;
            visited.clear();
            float minimum = INFINITY;
            for (const auto ptr : path_weights) {
                minimum = min(*ptr, minimum);
            }
            // cout << "minimum" << minimum << endl;
            for (auto ptr : path_weights) {
                (*ptr) -= minimum;
            }
            total += minimum;
            path_weights.clear();
        }
        return total;
    }
};

int matchings(int left, int right, const vector<pair<int, int>> &edges) {
    vector<vector<pair<int, float>>> E(left + right + 2,
                                       vector<pair<int, float>>());
    // cout << edges;
    int source = left + right;
    int drain = left + right + 1;
    for (int i = 0; i < left; ++i) {
        int l = i;
        E[source].push_back({l, 1});
        E[l].push_back({source, 0});
    }
    for (int i = 0; i < right; ++i) {
        int r = left + i;
        E[drain].push_back({r, 0});
        E[r].push_back({drain, 1});
    }
    // cout << "sources, drains" << endl;
    for (const auto &e : edges) {
        int a = e.first;
        int b = e.second + left;
        E[a].push_back({b, 1});
        E[b].push_back({a, 0});
    }
    // for (int e = 0; e < left + right + 2; ++e) {
    //     cout << "edge: " << e << endl;
    //     for (auto adj : E[e]) {
    //         cout << adj.first << ", w: " << adj.second << endl;
    //     }
    // }
    // cout << "Running FF" << endl;
    return FordFulkerson(E, source, drain).solve();
}

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

    // int desired_size[n];
    // int sizes[m];
    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];
    // cout << "here" << endl;
    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 << "here" << endl;
    // edges.push_back({a, b});
    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