code/dataStructures/XorBaseN.cc

View this file on GitHub
Last update: 2020-10-28 19:21:59+01:00
Link: https://codeforces.com/blog/entry/68953

Depends on

code/template.cc

Code

#include "../template.hh" // https://codeforces.com/blog/entry/68953
template<int N>
struct XorBase : vector<bitset<N>> {
  using T = bitset<N>;
  static bool tryReduce(T& test, const T& other) {
    for (int i = N - 1; ~i; --i) {
      if (other[i]) {
        if (test[i]) return test ^= other, true;
        break;
      }
    }
    return false;
  }
  void apply(T& toApply) {
    for(const T& b : *this)
      tryReduce(toApply, b);
  }
  pair<bool, vector<bool>> to(T elem) {
    vector<bool> res(SZ(*this));
    F0R(i, SZ(*this))
      res[i] = tryReduce(elem, (*this)[i]);
    return mp(elem.none(), res);
  }
  bool isIn(T toCheck) {
    apply(toCheck);
    return toCheck.none();
  }
  bool add(T toAdd) {
    apply(toAdd);
    if(toAdd.any()) this->pb(toAdd);
    return toAdd.any();
  }
  XorBase(const vector<T>& elems) {
    for(const auto& e : elems) add(e);
  }
  XorBase() {};
};

#line 1 "code/template.cc"
// this line is here for a reason
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define endl '\n'
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(x) (int)(x).size()
#define FOR(a, b, c) for (auto a = (b); (a) < (c); ++(a))
#define F0R(a, b) FOR (a, 0, (b))
template <typename T>
bool ckmin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <typename T>
bool ckmax(T& a, const T& b) { return a < b ? a = b, true : false; }
#ifndef DEBUG
#define DEBUG 0
#endif
#define dout if (DEBUG) cerr
#define dvar(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#line 2 "code/dataStructures/XorBaseN.cc"
template<int N>
struct XorBase : vector<bitset<N>> {
  using T = bitset<N>;
  static bool tryReduce(T& test, const T& other) {
    for (int i = N - 1; ~i; --i) {
      if (other[i]) {
        if (test[i]) return test ^= other, true;
        break;
      }
    }
    return false;
  }
  void apply(T& toApply) {
    for(const T& b : *this)
      tryReduce(toApply, b);
  }
  pair<bool, vector<bool>> to(T elem) {
    vector<bool> res(SZ(*this));
    F0R(i, SZ(*this))
      res[i] = tryReduce(elem, (*this)[i]);
    return mp(elem.none(), res);
  }
  bool isIn(T toCheck) {
    apply(toCheck);
    return toCheck.none();
  }
  bool add(T toAdd) {
    apply(toAdd);
    if(toAdd.any()) this->pb(toAdd);
    return toAdd.any();
  }
  XorBase(const vector<T>& elems) {
    for(const auto& e : elems) add(e);
  }
  XorBase() {};
};