Task solution

[Snaksa]

Hello! I saw this task today and tought about it for a while (there is short version after it):

A bench in the subway has n places, marked with the numbers from 1 up to n. In the beginning the bench is empty – all the n places are vacant. In order, one by one, from the subway entry a person enters. He sits in the middle place of the first maximal continuous sequence of empty places. In case that maximal sequence of empty places contains an even number of places, the person sits in the place with the smaller number among the two middle places in this sequence.
For example, if the bench has n = 6 places, the first person sits in place 3, because there is a unique sequence of empty places – from place 1 to 6, which contains an odd number of places, and 3 is the place with a smaller number among the two middle places (3 and 4) of this sequence. For the second person there are two sequences to choose from – from 1 to 2 and from 4 to 6. The sequence from 4 to 6 is maximal, containing 3 places, and the second person sits in its center – place 5.The third person sits in place 1 – the middle place for the sequence of places 1 to 2, the fourth person – in place 2, the fifth – in place 4 and the sixth – in place 6.
Write a program bench, which finds the place in which a particular person sits, and given a place, which person sits on it.
Input
From the standard input you should read three natural numbers: n i p, with interval between them, where:
• n is the total number of places of the bench,
• i means the i-th person, and
• p means the p-th place in the bench.
Output
Write to the standard output two numbers q and j, with an interval between them, for which it is true that:
• i-th person sits in place q, and
• j-th person sits in place p.
Constraints
1 ≤ i, p ≤ n ≤ 10¹⁶
In 20% of the tests, n < 10000.
In another 30% of the tests, n = 2k-1, where k>0 is an integer.

Example:
Input : 6 1 5
Output: 3 2

Short version: Let's say that I have 10 seats. I need to find the middle of this sequence of numbers (1-10). The middle seat is 5. Then I need to find the middle seat of the largest maximal continuous sequence. Right now I have two sequences. The first one is from 1 to 4 and the second one is from 6 to 10. Number 5 is already taken. I find that the largest sequence is from 6-10. And the middle seat is 8. I should do that until every seat is taken.

I wrote my own solution but it works with 2D array and as you can think it do not work well with large values of n. First it is too slow and second I can't make array with 10¹⁶ elements.
Can you suggest a solution that is fast and works with large values of n? Maybe something like Bitwise Operations? I don't know. Any help will be very appreciated. :)

[cire]

Maybe something like this?

#include <utility>
#include <deque>
#include <queue>
#include <cassert>

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;
}

http://ideone.com/e8U7JB

[Smac89]

What are the time constraints on this?

E: If there was more than one space on the bench that had the same number of seats, does it matter if we place somebody on any one of the spots or do we have to place them in the lower range seats?