Code: Interval Game

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

static int64 count_disjoint_leq(int64 limit, int64 mask) {
    if (limit < 0) return 0;
    int64 ans = 0;
    bool tight = true;

    for (int bit = 20; bit >= 0; --bit) {
        const int m = (mask >> bit) & 1;
        const int l = (limit >> bit) & 1;
        if (!tight) continue;

        if (l == 1) {
            int free_bits = 0;
            for (int b = bit - 1; b >= 0; --b) {
                if (((mask >> b) & 1) == 0) ++free_bits;
            }
            ans += (1LL << free_bits);

            if (m == 1) {
                tight = false;
            }
        }
    }

    if (tight) ++ans;
    return ans;
}

void solve() {
    int x1, x2;
    cin >> x1 >> x2;

    const int m = x1 - 1;
    const int n = x2 - 1;

    int best_t = 0;
    int64 best_lose = (1LL << 62);

    for (int t = 0; t <= m; ++t) {
        int64 lose = 0;
        if (t <= n) {
            const int64 M = (n - t) / 2;
            const int64 ways_u = count_disjoint_leq(M, t);
            const int64 ways_split = 1LL << __builtin_popcount((unsigned)t);
            lose = ways_u * ways_split;
        }
        if (lose < best_lose) {
            best_lose = lose;
            best_t = t;
        }
    }

    // Choose (a, b) = (best_t, 0): a xor b = best_t and a + b <= m.
    const int l1 = best_t + 1;
    const int r1 = x1;
    cout << l1 << ' ' << r1 << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tc;
    cin >> tc;
    while (tc--) solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

using ll = int64_t;
void solve() {
    ll X1, X2;
    cin >> X1 >> X2;
    X1--;
    X2--;

    // denom = (X2+1)(X2+2)/2
    // numerator = floor(X2/2) + 1
    // play 1 1: probability that
    // ll P1 = (X2/2) + 1;
    // ll P2 = probability that XOR is nonzero

    map<int, int> del;
    for (int i = 0; i <= X2; i++) {
        int minj = 0;
        int maxj = X2 - i;
        maxj++;
        for (int b = 20; b >= 0; b--) {
            if (minj + (1 << b) <= maxj) {
                int f = i ^ minj;
                f &= ~((1 << b) - 1);
                del[f]++;
                del[f + (1 << b)]--;
                minj += (1 << b);
            }
        }
    }
    int best = -1;
    int best_freq = 1e9;
    int cnt = 0;
    for (int c = 0; c <= X1; c++) {
        cnt += del[c];
        if (cnt < best_freq) {
            best_freq = cnt;
            best = c;
        }
    }
    cout << 1 << ' ' << (X1 + 1 - best) << '\n';
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--)
        solve();
}