Submission #1604369

---

Source Code Expand

// #include {{{
#include <array>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
#include <iterator>
#include <tuple>
#include <utility>
#include <random>
#include <limits>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cstdint>
#include <cassert>

#ifdef DEBUG
#include <fmt/format.h>
#endif
// }}}

using namespace std;

// macros {{{
template<typename T, size_t N>
constexpr size_t NELEMS(T (&)[N]) { return N; }

template<typename InputIt>
void PRINT_RANGE(InputIt first, InputIt last)
{
    for(; first != last; ++first)
        cout << *first << (first==last ? "" : " ");
    cout << "\n";
}

template<typename T>
void PRINT_MATRIX(T mat, size_t nr, size_t nc)
{
    for(size_t r = 0; r < nr; ++r) {
        for(size_t c = 0; c < nc; ++c) {
            cout << mat[r][c] << (c==nc-1 ? "" : " ");
        }
        cout << "\n";
    }
}

#define FOR(i, start, end) for(int i = (start); i < (end); ++i)
#define REP(i, n) FOR(i, 0, n)
// }}}

// types {{{
using ll  = int64_t;
using ull = uint64_t;
// }}}

template<typename T>
T ceilpow2(T n)
{
    assert(n >= 0);
    if(n == 0) return T(1);

    int r = static_cast<int>(floor(log2(static_cast<long double>(n)))) + 1;
    return T(1) << r;
}

template<typename T>
T floorpow2(T n)
{
    assert(n > 0);

    int r = static_cast<int>(floor(log2(n)));
    return T(1) << r;
}

uint32_t flp2(uint32_t n)
{
    assert(n > 0);

    n = n | (n >>  1);
    n = n | (n >>  2);
    n = n | (n >>  4);
    n = n | (n >>  8);
    n = n | (n >> 16);
    return n - (n >> 1);
}

uint64_t flp2(uint64_t n)
{
    assert(n > 0);

    n = n | (n >>  1);
    n = n | (n >>  2);
    n = n | (n >>  4);
    n = n | (n >>  8);
    n = n | (n >> 16);
    n = n | (n >> 32);
    return n - (n >> 1);
}

uint32_t clp2(uint32_t n)
{
    if(n == 0) return 1;

    --n;
    n = n | (n >>  1);
    n = n | (n >>  2);
    n = n | (n >>  4);
    n = n | (n >>  8);
    n = n | (n >> 16);
    return n + 1;
}

uint64_t clp2(uint64_t n)
{
    if(n == 0) return 1;

    --n;
    n = n | (n >>  1);
    n = n | (n >>  2);
    n = n | (n >>  4);
    n = n | (n >>  8);
    n = n | (n >> 16);
    n = n | (n >> 32);
    return n + 1;
}

ull A, B;

void solve()
{
    if(A == B) {
        cout << 1 << "\n";
        return;
    }

    cout << floor(log2(static_cast<double>(0b11111111111111111111111111111111111111111111111111111111111))) << "\n";
    cout << floor(log2(static_cast<long double>(0b11111111111111111111111111111111111111111111111111111111111))) << "\n";

#ifdef DEBUG
    fmt::print("A:\t{:b}\n", A);
    fmt::print("B:\t{:b}\n", B);
    fmt::print("A^B:\t{:b}\n", A^B);
#endif

    //ull T2 = ceilpow2(A ^ B);
    ull T2 = flp2(A ^ B) << 1;
    A &= T2-1;
    B &= T2-1;
    ull T = T2 >> 1;

    ull xmin = A;
    ull xmax = T-1;

    //ull K = ceilpow2(B & (T-1));
    ull BL = B & (T-1);
    ull K = BL == 0 ? 1 : flp2(B & (T-1)) << 1;

    ull ymin = T;
    ull ymax = T + K - 1;

    ull xymin = T+A;
    ull xymax = 2*T - 1;

#ifdef DEBUG
    fmt::print("A:\t{:b}\n", A);
    fmt::print("B:\t{:b}\n", B);
    fmt::print("T2:\t{:b}\n", T2);
    fmt::print("T:\t{:b}\n", T);
    fmt::print("K:\t{:b}\n", K);
    fmt::print("xmin:\t{:b}\n", xmin);
    fmt::print("xmax:\t{:b}\n", xmax);
    fmt::print("ymin:\t{:b}\n", ymin);
    fmt::print("ymax:\t{:b}\n", ymax);
    fmt::print("xymin:\t{:b}\n", xymin);
    fmt::print("xymax:\t{:b}\n", xymax);
#endif

    ull ans = xmax - xmin + 1;
    if(ymax < xymin) {
        ans += ymax  - ymin  + 1;
        ans += xymax - xymin + 1;
    }
    else {
        ans += xymax - ymin + 1;
    }

    cout << ans << "\n";
}

int main()
{
    cin >> A >> B;

    solve();

    return 0;
}

Submission Info

Judge Result