目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

G - Library of Magic

---

二、解题报告

1、思路分析

首先 query(1, n) = a ^ b ^ c

如果 query(1, n) > 0

那么我们可以一次二分找到 a, 再一次二分找到b，那么 c = query(1, n) ^ a ^ b

为甚么可以二分？因为 我们能二分出 最小得满足 [1, a] > 0 的 a，继而能二分出 最小的满足[a + 1, b] > 0 的 b

如果 query(1, n) == 0，说明甚么？

说明b, c 第 i 位为1，a 第 i 位为 0（因为 a, b, c 互异，一定成立）

我们从0，60 不断查询 (1, (1 << i) - 1)，第一个满足查询结果 res > 0，说明找到了 a，break

然后一次二分，在[a + 1, n] 中找到 b，然后 c = query(1, n) ^ a ^ b

2、复杂度

时间复杂度： O(logn)空间复杂度：O(1)

3、代码详解

 ​

#include <bits/stdc++.h>

// #define DEBUG

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;

i64 query(i64 l, i64 r) {
    if (l > r) {
        return 0LL;
    }

    std::cout << "xor " << l << ' ' << r << std::endl;

    i64 res;
    std::cin >> res;

    return res;
}

void solve() {
    i64 n;
    std::cin >> n;

    i64 st = query(1, n);

    i64 a = -1, b = -1, c = 1;

    if (st > 0) {
        i64 lo = 1, hi = n;
        while (lo < hi) {
            i64 x = (lo + hi) / 2;
            if (query(1, x) > 0) {
                hi = x;
            } else {
                lo = x + 1;
            }
        }

        a = hi;

        lo = a + 1;
        hi = n;

        while (lo < hi) {
            i64 x = (lo + hi) / 2;
            if (query(a + 1, x) > 0) {
                hi = x;
            } else {
                lo = x + 1;
            }
        }

        b = hi;
        c = st ^ a ^ b;
    } else {
        for (int i = 0; i < 60; ++ i) {
            if ((1LL << i) > n) {
                assert(false);
            }

            i64 res = query(1, (1LL << i) - 1);
            if (res > 0) {
                a = res;
                break;
            }
        }

        i64 lo = a + 1, hi = n;

        while (lo < hi) {
            i64 x = (lo + hi) / 2;

            if (query(a + 1, x) > 0) {
                hi = x;
            } else {
                lo = x + 1;                
            }
        }

        b = hi;
        c = st ^ a ^ b;
    }

    for (auto x : {a, b, c}) {
        assert(x != -1);
    }

    std::cout << "ans " << a << ' ' << b << ' ' << c << std::endl;
}

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

#ifdef DEBUG
    int START = clock();
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    int t = 1;
    std::cin >> t;

    while (t --) {
        solve();
    }
#ifdef DEBUG
    std::cerr << "run-time: " << clock() - START << '\n';
#endif
    return 0;
}