text: // https://projecteuler.net/problem=61
  /*
  Cyclical figurate numbers
  Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal)
  numbers and are generated by the following formulae:
  
  Triangle	 	P3,n=n(n+1)/2	 	1, 3,  6, 10, 15, ...
  Square	 		P4,n=n2	 			1, 4,  9, 16, 25, ...
  Pentagonal	 	P5,n=n(3n-1)/2	 	1, 5, 12, 22, 35, ...
  Hexagonal	 	P6,n=n(2n-1)	 	1, 6, 15, 28, 45, ...
  Heptagonal	 	P7,n=n(5n-3)/2	 	1, 7, 18, 34, 55, ...
  Octagonal	 	P8,n=n(3n-2)	 	1, 8, 21, 40, 65, ...
  The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three uint32_teresting properties.
  
  The set is cyclic, in that the last two digits of each number is the first two digits of the next number
  (including the last number with the first).
  Each polygonal type: triangle (P3,127=8128), square (P4,91=8281), and pentagonal (P5,44=2882), is represented
  by a different number in the set.
  This is the only set of 4-digit numbers with this property.
  Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle,
  square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.
  
  Solution:
  */
  
  #include <iostream>
  #include <cstdint>
  #include <vector>
  #include <algorithm>
  #include <functional>
  #include <numeric>
  #include <chrono>
  using namespace std;
  
  vector<vector<uint32_t>> polyNumbers;
  void pushPolygonalNumbers(uint32_t a, uint32_t b) {
  	vector<uint32_t> set;
  	uint32_t n = 1, i = a;
  	while (n < 1000) {
  		n += i;
  		i += b;
  	}
  	while (n < 10000) {
  		if ((n % 100) / 10) // second last digit should not be 0
  			set.push_back(n);
  		n += i;
  		i += b;
  	}
  	polyNumbers.emplace_back(set);
  }
  
  template<class T>
  inline auto getIndex(const vector<T>& ary, const T& val) {
  	return lower_bound(begin(ary), end(ary), val) - begin(ary);
  }
  
  vector<uint32_t> cyclicNumbers;
  bool dfs(const uint32_t matched, const uint32_t idx = 0) {
  	const auto n = cyclicNumbers.size();
  	if (matched == (1 << n) - 1) {
  		if ((cyclicNumbers.front() / 100) == (cyclicNumbers.back() % 100)) {
  			// check for duplicate numbers
  			sort(begin(cyclicNumbers), end(cyclicNumbers));
  			for (size_t i = 1; i < n; ++i)
  				if (cyclicNumbers[i] == cyclicNumbers[i - 1])
  					return false;
  			return true;
  		}
  		return false;
  	}
  
  	uint32_t last2 = cyclicNumbers[idx] % 100;
  	for (uint32_t i = 1; i < n; ++i) {
  		if (!(matched & (1 << i))) {
  			const uint32_t str = getIndex(polyNumbers[i], last2 * 100);
  			const uint32_t end = getIndex(polyNumbers[i], (last2 + 1) * 100);
  			for (uint32_t j = str; j < end; ++j) {
  				cyclicNumbers[idx + 1] = polyNumbers[i][j];
  				if (dfs(matched | (1 << i), idx + 1))
  					return true;
  			}
  		}
  	}
  	return false;
  }
  
  auto get(const vector<uint32_t> &set) {
  	for (const auto& val : set)
  		pushPolygonalNumbers(val - 1, val - 2);
  
  	cyclicNumbers.resize(set.size());
  	for (uint32_t i = getIndex(polyNumbers[0], 1000U), n = polyNumbers[0].size(); i < n; ++i) {
  		cyclicNumbers[0] = polyNumbers[0][i];
  		if (dfs(1))
  			break;
  	}
  
  	return accumulate(begin(cyclicNumbers), end(cyclicNumbers), 0);
  }
  
  auto compute() {
  	return get({ 8,7,6,5,4,3 });
  }
  
  #ifdef _MSC_VER
  	template <class T>
  	inline void DoNotOptimize(const T &value) {
  		__asm { lea ebx, value }
  	}
  #else
  	template <class T>
  	__attribute__((always_inline)) inline void DoNotOptimize(const T &value) {
  		asm volatile("" : "+m"(const_cast<T &>(value)));
  	}
  #endif
  
  int main() {
  	using namespace std;
  	using namespace chrono;
  	auto start = high_resolution_clock::now();
  	auto result = compute();
  	DoNotOptimize(result);
  	cout << "Done in "
  		<< duration_cast<nanoseconds>(high_resolution_clock::now() - start).count() / 1e6
  		<< " miliseconds." << endl;
  	cout << result << endl;
  }