fork(1) download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <numeric>
  4. #include <vector>
  5. using namespace std;
  6.  
  7. bool is_valid_placement(const auto& cur, const auto& end) {
  8.     size_t n = distance(cur, end);
  9.     vector<uint32_t> diag_1(2 * n + 1, 0),
  10.                      diag_2(2 * n + 1, 0);
  11.  
  12.     size_t row_index = 1;
  13.     for_each(cur, end, [&](uint64_t row) {
  14.         diag_1[__builtin_ctzll(row) + 1 + row_index] ++;
  15.         diag_2[__builtin_ctzll(row) + 1 - row_index + n] ++;
  16.         row_index ++;
  17.     });
  18.  
  19.     return *max_element(diag_1.cbegin(), diag_1.cend()) == 1 &&
  20.            *max_element(diag_2.cbegin(), diag_2.cend()) == 1;
  21. }
  22.  
  23. int main() {
  24.     size_t n;
  25.     cin >> n;
  26.  
  27.     vector<uint64_t> board(n);
  28.     iota(board.begin(), board.end(), 0);
  29.     for_each(board.begin(), board.end(), [](uint64_t& row) { row = uint64_t(1) << row; });
  30.  
  31.     size_t answer = 0;
  32.     do {
  33.         if (is_valid_placement(board.cbegin(), board.cend()))
  34.             answer ++;
  35.     } while (next_permutation(board.begin(), board.end()));
  36.  
  37.     cout << answer << endl;
  38.     return 0;
  39. }
  40.  
Success #stdin #stdout 0.04s 4452KB
comments (?)
stdin
copy 
9
stdout
copy 
352
https://ideone.com/bMIBpN
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!