続・PFIサマーインターン2011問題

今更ですが、これの続き。
前回は最悪がO(n²)だったので、最悪をO(n)にしました。

#include <assert.h>
#include <algorithm>
#include <string>

char pfi2011(std::string& s)
{
    assert(!s.empty());
    typedef std::string::iterator iter_t;
    iter_t l = s.begin(), r = s.end();
    iter_t const mid = l + s.size()/2;
    for (unsigned char mask = 1; mask; mask <<= 1) {
        iter_t const it =
            std::partition(l, r,
                           [mask](unsigned c) noexcept -> bool {
                               return c & mask;
                           });
        if (it < mid)
            l = it;
        else
            r = it;
    }
    return *mid;
}

書くのは簡単ですね。