Language: C++



#include <cstdio>
#include <functional>
#include <iostream>
#include <random>
#include <set>
#include <unordered_map>
#include <vector>
using namespace std;

class MaximumMatching {
 public:
  struct Edge {
    int from, to;
  };

  MaximumMatching(int N, const vector<Edge>& raw_edges) : N(N) {
    ofs.assign(N + 2, 0);
    for (auto& e : raw_edges) ++ofs[e.from + 1], ++ofs[e.to + 1];
    for (int i = 1; i <= N + 1; ++i) ofs[i] += ofs[i - 1];
    edges.resize(2 * raw_edges.size());
    for (auto& e : raw_edges) {
      edges[ofs[e.from]++] = {e.from, e.to};
      edges[ofs[e.to]++] = {e.to, e.from};
    }
    for (int i = N + 1; i > 0; --i) ofs[i] = ofs[i - 1];
    ofs[0] = 0;
  }

  int maximum_matching() {
    vector<int> label(N + 1, -1), mate(N + 1, 0), first(N + 1, 0);
    vector<int> que(N);
    int qh = 0, qt = 0;

    auto enqueue = [&](int v) { que[qt++] = v; };
    auto dequeue = [&] { return que[qh++]; };
    auto encode = [&](int eid) { return (N + 1) + eid; };
    auto decode = [&](int h) { return h - (N + 1); };

    function<int(int)> find_first = [&](int v) {
      return label[first[v]] < 0 ? first[v] : first[v] = find_first(first[v]);
    };

    function<void(int, int)> rematch = [&](int v, int w) {
      auto t = mate[v];
      mate[v] = w;
      if (mate[t] != v) return;
      if (label[v] <= N) {
        mate[t] = label[v];
        rematch(label[v], t);
      } else {
        auto& e = edges[decode(label[v])];
        int x = e.from, y = e.to;
        rematch(x, y);
        rematch(y, x);
      }
    };

    auto contract = [&](int x, int y, int eid) {
      int r = find_first(x), s = find_first(y);
      if (r == s) return;
      auto h = encode(eid);
      label[r] = label[s] = -h;
      int join = -1;  // mate[lca]
      while (1) {
        if (s != 0) swap(r, s);
        r = find_first(label[mate[r]]);
        if (label[r] == -h) {
          join = r;
          break;
        } else
          label[r] = -h;
      }
      for (auto v : {first[x], first[y]}) {
        for (; v != join; v = first[label[mate[v]]]) {
          label[v] = h;
          first[v] = join;
          enqueue(v);
        }
      }
    };

    auto augmented = [&](int u) {
      label[u] = first[u] = 0;
      for (qh = qt = 0, enqueue(u); qh < qt;) {
        auto x = dequeue();
        for (int eid = ofs[x]; eid < ofs[x + 1]; ++eid) {
          auto y = edges[eid].to;
          if (mate[y] == 0 && y != u) {
            mate[y] = x;
            rematch(x, y);
            return true;
          } else if (label[y] >= 0) {
            contract(x, y, eid);
          } else if (label[mate[y]] < 0) {
            label[mate[y]] = x;
            first[mate[y]] = y;
            enqueue(mate[y]);
          }
        }
      }
      return false;
    };

    int match = 0;
    for (int u = 1; u <= N; ++u)
      if (mate[u] == 0 && augmented(u)) {
        match += 1;
        if (N - 2 * match <= 1) break;
        if (10 * qt < N) {
          label[0] = -1;
          for (int qi = 0; qi < qt; ++qi) {
            label[que[qi]] = label[mate[que[qi]]] = -1;
          }
        } else
          fill(label.begin(), label.end(), -1);
      }
    return match;
  }

 private:
  int N;
  vector<int> ofs;
  vector<Edge> edges;
};
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(a) begin(a), end(a)
#define let const auto
signed main() {
  int n;
  cin >> n;
  vector<int> A(n);
  vector<int> p2s = {2,        4,         8,         16,        32,
                     64,       128,       256,       512,       1024,
                     2048,     4096,      8192,      16384,     32768,
                     65536,    131072,    262144,    524288,    1048576,
                     2097152,  4194304,   8388608,   16777216,  33554432,
                     67108864, 134217728, 268435456, 536870912, 1073741824};

  unordered_map<int, int> t;
  REP(i, n) cin >> A[i];
  sort(ALL(A));
  REP(i, n) {
    let a = A[i];
    if (t.find(a) == t.end())
      t[a] = 1;
    else
      t[a]++;
  }
  using Edge = MaximumMatching::Edge;
  vector<Edge> edges;
  unordered_map<int, int> i2a;
  vector<int> is;
  REP(i, n) {
    let a = A[i];
    REP(j, p2s.size()) {
      let k2 = p2s[j] - a;
      if (k2 > a) break;
      if (t.find(k2) == t.end()) continue;
      let c = t[k2];
      i2a[a] = 0;
      is.push_back(a);
      REP(k, c) {
        let b = k2 + 1073741824 * k;
        edges.push_back({b, a});
        i2a[b] = 0;
        is.push_back(b);
      }
    }
  }
  sort(ALL(is));
  int index = 1;
  REP(i, is.size()) {
    let s = is[i];
    if (i > 0 && s == is[i - 1]) continue;
    i2a[s] = index;
    index++;
  }
  REP(i, edges.size()) { edges[i] = {i2a[edges[i].from], i2a[edges[i].to]}; }
  // TODO: normalize edges
  // REP(i, edges.size()) cout << edges[i].from << " " << edges[i].to << endl;
  // cout << "aa" << endl;
  auto mm = MaximumMatching(n, edges);
  auto ans = mm.maximum_matching();
  cout << ans << endl;
  return 0;
}

Compiler output:
a.cc: In function 'int main()':
a.cc:143:3: error: 'sort' was not declared in this scope; did you mean 'sqrt'?
  143 |   sort(ALL(A));
      |   ^~~~
      |   sqrt