#include <iostream>
#include <thread>
#include <vector>
#include <memory>
#include <atomic>

/* wrapping-structure for using vector which element is std::atomic<T> */
/* because vector's element must be copy-constructible and copy-assignable but atomic<T> is not. */
/* https://stackoverflow.com/questions/13193484/how-to-declare-a-vector-of-atomic-in-c */

template <typename T>
struct atomicwrapper {
  std::atomic<T> _a;
  atomicwrapper() : _a() {}
  atomicwrapper(const std::atomic<T> &a) : _a(a.load()) {}
  atomicwrapper(const atomicwrapper &obj) : _a(obj._a.load()) {}
  atomicwrapper &operator=(const atomicwrapper &obj) { _a.store(obj._a.load()); }
};

void divmod(int64_t a, int64_t b, int64_t &q, int64_t &r) { q = a / b; r = a % b; }

using T = int;
class MyVectorBool {

private:
  static constexpr T width = sizeof(T) * 8;
  static constexpr T bits = width - 1;
  static constexpr T mask_dirty = 1 << bits;

  std::vector<atomicwrapper<T>> _myVectorBool;
  int64_t _size;

public:
  MyVectorBool() = delete;
  MyVectorBool(int64_t size) {
    _size = size;
    _myVectorBool = std::vector<atomicwrapper<T>>((_size - 1) / bits + 1);
    for (auto &c : _myVectorBool)
      c._a.store(0);
  }

  bool test(int64_t index) {
    if (index >= _size) throw 1;
    int64_t q, r;
    divmod(index, bits, q, r);
    T elements;
    for (;;) {
      elements = _myVectorBool[q]._a.load();
      if (!(elements & mask_dirty)) break;
    }
    return ((elements & (1 << r)) != 0);
  }

#define MACRO_CAS(V) \
    for (;;) { \
      T before_cas; \
      V = before_cas = _myVectorBool[q]._a.load(); /* preliminary data-loading */ \
      if (V & mask_dirty) continue; /* if elment's dirty bit is on, spin lock */ \
    CAS_START: \
      if (_myVectorBool[q]._a.compare_exchange_weak(/*ref*/V, V | mask_dirty)) { \
        /* when exchange-able, status is not dirty, nothing to do */ \
      } else if (/*returned */ V != before_cas) { \
        /* when not-change-able and atomic-value is actually change, spin lock */ \
        continue; \
      } else { \
        /* when not-change-able and yet atomic-value is same befor and after CAS (it's called weak-CAS's Spurious Failure), do CAS again */ \
        goto CAS_START; \
      } \
      break; \
    }
/* end of macro */

  void set(int64_t index) {
    if (index >= _size) return;
    int64_t q, r;
    divmod(index, bits, q, r);
    T elements;

    MACRO_CAS(elements)

    elements |= 1 << r;
    _myVectorBool[q]._a.store(elements);
  }

  void reset(int64_t index) {
    if (index >= _size) return;
    int64_t q, r;
    divmod(index, bits, q, r);
    T elements;

    MACRO_CAS(elements)

    T mask = 1 << r;
    elements &= ~mask;
    _myVectorBool[q]._a.store(elements);
  }
};
/*------------------------------------------------*/

int const A = 60; /* test A */
int const B = 15; /* test B */

MyVectorBool vb1(A);
MyVectorBool vb2(B);

void worker(int i) {
  vb2.set(i);
}

int main() {
  /* test A */
  for (int i = 0; i < A; i++) {
    std::cout << "set: i = " << i << " : ";
    vb1.set(i);
    if (vb1.test(i)) std::cout << "OK" << std::endl;
    else { std::cout << "NG" << std::endl; return 0; }
  }
  for (int i = 0; i < A; i++) {
    std::cout << "reset: i = " << i << " : ";
    vb1.reset(i);
    if (!vb1.test(i)) std::cout << "OK" << std::endl;
    else { std::cout << "NG" << std::endl; return 0; }
  }

  /* test B */
  std::cout << "core.n = " << std::thread::hardware_concurrency() << std::endl;

  for (int i = 0; i < B; i++)
    std::cout << (vb2.test(i) ? "1" : "0");
  std::cout << std::endl;
  
  std::vector<std::shared_ptr<std::thread>> threads(B);
  int i = 0;
  for (std::shared_ptr<std::thread> &t : threads)
    t = std::make_shared<std::thread>(worker, i++);
  
  for (std::shared_ptr<std::thread> t : threads)
    t->join();

  for (int i = 0; i < B; i++)
    std::cout << (vb2.test(i) ? "1" : "0");
  std::cout << std::endl;

  return 0;
}
/* end */