Fixed points

#include <iostream>
#include <string>
#include <vector>
#include <cstdint>

bool nth_bit_of(uint64_t val, int n)
{
    uint64_t mask = (uint64_t)(1) << n;
    return bool(mask & val);
}

uint64_t prepend_nth(uint64_t x, bool truthiness, int n)
{
    if (truthiness) {
        return x + ((uint64_t)(1) << n);
    }
    else {
        return x;
    }
}

int find_C(uint64_t a, uint64_t x, int n)
{
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        if (nth_bit_of(a, i) && nth_bit_of(x, n - i)) sum++;
    }
    return sum;
}

void foo(bool a, bool b, bool C, bool& xFalseOk, bool& xTrueOk)
{
    xFalseOk = false;
    xTrueOk = false;

    if (a) {
        // 1 x x
        if (b) {
            // 1 1 x
            if (C) {
                // 1 1 1
                xFalseOk = true;
                xTrueOk = true;
            }
        }
        else {
            // 1 0 x
            if (!C) {
                // 1 0 0
                xFalseOk = true;
                xTrueOk = true;
            }
        }
    }
    else {
        // 0 x x
        if (b) {
            // 0 1 x
            if (C) {
                // 0 1 1
                xFalseOk = true;
            }
            else {
                // 0 1 0
                xTrueOk = true;
            }
        }
        else {
            // 0 0 x
            if (C) {
                // 0 0 1
                xTrueOk = true;
            }
            else {
                // 0 0 0
                xFalseOk = true;
            }
        }
    }
}

uint64_t find_fixed_point(uint64_t a, uint64_t b)
{
    struct Candidate {
        Candidate(uint64_t p, int n, int c) : prefix(p), n(n), carry(c) {}

        uint64_t prefix = 0;
        int n = 0;
        int carry = 0;
    };

    std::vector<Candidate> candidates;
    candidates.emplace_back(0, 0, 0);

    while (!candidates.empty()) {
        auto candidate = candidates.back();
        candidates.pop_back();

        auto x = candidate.prefix;
        auto n = candidate.n;

        if (((a * x) ^ b) == x) return x;
        if (n == 64) continue;

         // std::cerr << "Trying to append bit " << n << " to " << x << std::endl;

        auto bit_a = nth_bit_of(a, 0);
        auto bit_b = nth_bit_of(b, n);

        auto C = candidate.carry + find_C(a, x, n);
        auto carry = C / 2;
        bool bit_C = C % 2;

         // std::cerr << "a: " << bit_a << " b: " << bit_b << " C: " << bit_C << std::endl;

        bool xFalseOk, xTrueOk;
        foo(bit_a, bit_b, bit_C, xFalseOk, xTrueOk);

        if (!xFalseOk && !xTrueOk) continue;

        if (xFalseOk) {
             // std::cerr << "0 bit OK" << std::endl;
            auto xx = prepend_nth(x, false, n);
            candidates.emplace_back(xx, n + 1, carry);
        }
        if (xTrueOk) {
             // std::cerr << "1 bit OK" << std::endl;
            auto xx = prepend_nth(x, true, n);
            candidates.emplace_back(xx, n + 1, carry + ((bit_a && bit_C) ? 1 : 0));
        }
         // std::cerr << std::endl;
    }

    return 0;
}

int main()
{
    int t;
    std::cin >> t;


    std::vector<std::pair<uint64_t, uint64_t>> abs;
    for (int ti = 0; ti < t; ++ti) {
        uint64_t a;
        uint64_t b;
        std::cin >> a >> b;
        abs.push_back(std::make_pair(a, b));
    }

    for (const auto& ab : abs) {
        auto a = ab.first;
        auto b = ab.second;

        if (b == 0) {
            std::cout << "0" << std::endl;
        }
        else {
            auto ret = find_fixed_point(a, b);
            if (ret != 0) {
                std::cout << ret << std::endl;
            }
            else {
                std::cout << "-" << std::endl;
            }
        }
    }
}

Test 1

Verdict: ACCEPTED