fork(1) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <utility>
  4. #include <queue>
  5. #include <cassert>
  6. #include <deque>
  7. #include <cstdlib>
  8.  
  9. typedef std::pair<std::size_t, std::size_t> solution_type;
  10. typedef std::pair<std::size_t, std::size_t> range_type;
  11.  
  12. struct range_compare
  13. {
  14.     bool operator()(const range_type& a, const range_type& b)
  15.     {
  16.         const std::size_t a_size = a.second - a.first;
  17.         const std::size_t b_size = b.second - b.first;
  18.  
  19.         if (a_size < b_size)
  20.             return true;
  21.  
  22.         if (a_size > b_size)
  23.             return false;
  24.  
  25.         return a.first > b.first;
  26.     }
  27. };
  28.  
  29. solution_type find_solution(std::size_t nSpaces, std::size_t nthPerson, std::size_t nthSpace)
  30. {
  31.     assert(nSpaces > 0 && nthPerson <= nSpaces && nthSpace <= nSpaces);
  32.  
  33.     std::priority_queue<range_type, std::deque<range_type>, range_compare> bench((range_compare()));
  34.     bench.emplace(1, nSpaces);
  35.  
  36.     solution_type result( nthPerson == nSpaces ? nthPerson : 0, nthSpace == nSpaces ? nthSpace : 0);
  37.  
  38.     unsigned i = 1;
  39.     while (!result.first || !result.second)
  40.     {
  41.         assert(!bench.empty());
  42.  
  43.         const auto range = bench.top();
  44.         bench.pop();
  45.  
  46.         const std::size_t range_size = range.second - range.first + 1;
  47.         const std::size_t middle = range.first + (range_size / 2) - (range_size % 2 ? 0 : 1);
  48.  
  49.         if (middle == nthSpace)
  50.             result.second = i;
  51.  
  52.         if (i++ == nthPerson)
  53.             result.first = middle;
  54.  
  55.         if (range_size > 1)
  56.         {
  57.             if (range.first != middle)
  58.                 bench.emplace(range.first, middle - 1);
  59.  
  60.             bench.emplace(middle + 1, range.second);
  61.         }
  62.     }
  63.  
  64.     return result;
  65. }
  66.  
  67.  
  68. std::vector<std::vector<unsigned>> test_bench =
  69. { 
  70.     { 13, 5, 8, 14, 3, 15, 6, 9, 16, 1, 17, 7, 10, 18, 2, 11, 19, 4, 12, 20 },
  71.     { 14, 6, 8, 15, 2, 9, 16, 4, 10, 17, 1, 18, 7, 11, 19, 3, 12, 20, 5, 13, 21}
  72. };
  73.  
  74.  
  75. void test(const std::vector<unsigned>& v, unsigned nthPerson, unsigned nthSpace)
  76. {
  77.     auto solution = find_solution(v.size(), nthPerson, nthSpace);
  78.  
  79.     std::size_t place = std::find(v.begin(), v.end(), nthPerson) - v.begin() + 1;
  80.     std::size_t person = v[nthSpace-1];
  81.  
  82.     if (place != solution.first || person != solution.second)
  83.     {
  84.         std::cout << "Expected " << place << ", " << person << " for " 
  85.                   << nthPerson << ", " << nthSpace ;
  86.         std::cout << "\n\tGot " << solution.first << ", " << solution.second << '\n';
  87.  
  88.         std::exit(0);
  89.     }
  90. }
  91.  
  92. void test()
  93. {
  94.     for (unsigned i = 0; i < test_bench.size(); ++i)
  95.         for (unsigned j = 0; j < test_bench[i].size(); ++j)
  96.             for (unsigned k = 0; k < test_bench[i].size(); ++k)
  97.                 test(test_bench[i], j+1, k+1);
  98.  
  99.     std::cout << "Tests passed!\n";
  100. }
  101.  
  102.  
  103. int main()
  104. {
  105.     test();
  106. }
Success #stdin #stdout 0s 3436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Tests passed!
https://ideone.com/e8U7JB
language:
C++14 (gcc 8.3)
created:
10 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!