fork(2) download
copy 
  1. #include <iostream>
  2. #include <future>
  3. #include <atomic>
  4. using namespace std;
  5.  
  6. constexpr unsigned kBoardSize = 16;
  7. constexpr unsigned kThreads = 4;
  8.  
  9. constexpr unsigned kFirstBitInd = 21;
  10. constexpr uint64_t kFirstBit = 1ull << 21;
  11. constexpr uint64_t kAllColumns = ((1ull << kBoardSize) - 1) << kFirstBitInd;
  12.  
  13. std::atomic<unsigned> gRow = ATOMIC_VAR_INIT(kBoardSize / 2);
  14.  
  15. uint64_t solve_1(unsigned start_column)
  16. {
  17.     uint64_t stk[kBoardSize];
  18.     uint64_t free_columns = kAllColumns;
  19.     uint64_t free_diag_1 = ~0ull;
  20.     uint64_t free_diag_2 = ~0ull;
  21.     uint64_t cursor = kFirstBit << start_column;
  22.     uint64_t solutions = 0;
  23.     unsigned row = 0;
  24.  
  25.     do { // while (row)
  26.         while (cursor)
  27.         {
  28.             const uint64_t last_bit = cursor & -cursor;
  29.             if (!(free_columns ^ last_bit)) // or if (row == kBoardSize - 1)
  30.             {
  31.                 ++solutions;
  32.                 break;
  33.             }
  34.  
  35.             // next row
  36.             stk[row] = cursor;
  37.             ++row;
  38.             free_columns ^= last_bit;
  39.             free_diag_1 ^= last_bit;
  40.             free_diag_2 ^= last_bit;
  41.             free_diag_1 <<= 1;
  42.             free_diag_2 >>= 1;
  43.             cursor = free_columns & free_diag_1 & free_diag_2;
  44.         }
  45.  
  46.         // previous row
  47.         --row;
  48.         cursor = stk[row];
  49.         const uint64_t last_bit = cursor & -cursor;
  50.         free_columns ^= last_bit;
  51.         free_diag_1 >>= 1;
  52.         free_diag_2 <<= 1;
  53.         free_diag_1 ^= last_bit;
  54.         free_diag_2 ^= last_bit;
  55.         cursor ^= last_bit;
  56.     } while (row);
  57.  
  58.     return solutions;
  59. }
  60.  
  61. uint64_t solve_task()
  62. {
  63.     uint64_t sum = 0;
  64.     unsigned my_row = 0;
  65.  
  66.     while ((my_row = atomic_fetch_add(&gRow, 1u)) < kBoardSize)
  67.     {
  68.         auto res = solve_1(kBoardSize - my_row - 1);
  69.  
  70.         if ((kBoardSize & 1) == 0 || my_row != kBoardSize / 2)
  71.             res *= 2;
  72.  
  73.         sum += res;
  74.     }
  75.  
  76.     return sum;
  77. }
  78.  
  79. int main()
  80. {
  81.     std::future<uint64_t> fut[kThreads];
  82.     uint64_t sum = 0;
  83.  
  84.     for (auto& slot: fut)
  85.         slot = async(std::launch::async, solve_task);
  86.  
  87.     for (auto& slot: fut)
  88.         sum += slot.get();
  89.  
  90.     cout << sum << '\n';
  91. }
  92.  
Time limit exceeded #stdin #stdout 5s 36240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HavRN2
language:
C++14 (gcc 8.3)
created:
9 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!