#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <cassert>
#include <deque>
#include <cstdlib>

typedef std::pair<std::size_t, std::size_t> solution_type;
typedef std::pair<std::size_t, std::size_t> range_type;

struct range_compare
{
    bool operator()(const range_type& a, const range_type& b)
    {
        const std::size_t a_size = a.second - a.first;
        const std::size_t b_size = b.second - b.first;

        if (a_size < b_size)
            return true;

        if (a_size > b_size)
            return false;

        return a.first > b.first;
    }
};

solution_type find_solution(std::size_t nSpaces, std::size_t nthPerson, std::size_t nthSpace)
{
    assert(nSpaces > 0 && nthPerson <= nSpaces && nthSpace <= nSpaces);

    std::priority_queue<range_type, std::deque<range_type>, range_compare> bench((range_compare()));
    bench.emplace(1, nSpaces);

    solution_type result( nthPerson == nSpaces ? nthPerson : 0, nthSpace == nSpaces ? nthSpace : 0);

    unsigned i = 1;
    while (!result.first || !result.second)
    {
        assert(!bench.empty());

        const auto range = bench.top();
        bench.pop();

        const std::size_t range_size = range.second - range.first + 1;
        const std::size_t middle = range.first + (range_size / 2) - (range_size % 2 ? 0 : 1);

        if (middle == nthSpace)
            result.second = i;

        if (i++ == nthPerson)
            result.first = middle;

        if (range_size > 1)
        {
            if (range.first != middle)
                bench.emplace(range.first, middle - 1);

            bench.emplace(middle + 1, range.second);
        }
    }

    return result;
}


std::vector<std::vector<unsigned>> test_bench =
{ 
    { 13, 5, 8, 14, 3, 15, 6, 9, 16, 1, 17, 7, 10, 18, 2, 11, 19, 4, 12, 20 },
    { 14, 6, 8, 15, 2, 9, 16, 4, 10, 17, 1, 18, 7, 11, 19, 3, 12, 20, 5, 13, 21}
};


void test(const std::vector<unsigned>& v, unsigned nthPerson, unsigned nthSpace)
{
    auto solution = find_solution(v.size(), nthPerson, nthSpace);

    std::size_t place = std::find(v.begin(), v.end(), nthPerson) - v.begin() + 1;
    std::size_t person = v[nthSpace-1];

    if (place != solution.first || person != solution.second)
    {
        std::cout << "Expected " << place << ", " << person << " for " 
                  << nthPerson << ", " << nthSpace ;
        std::cout << "\n\tGot " << solution.first << ", " << solution.second << '\n';

        std::exit(0);
    }
}

void test()
{
    for (unsigned i = 0; i < test_bench.size(); ++i)
        for (unsigned j = 0; j < test_bench[i].size(); ++j)
            for (unsigned k = 0; k < test_bench[i].size(); ++k)
                test(test_bench[i], j+1, k+1);

    std::cout << "Tests passed!\n";
}


int main()
{
    test();
}