你好！作为你的教练，我非常高兴能为你梳理这道经典交互题的标准题解。

在信息学竞赛（NOIP/CSP）中，处理交互题（Interactive Problem）有两大核心铁律：

1. 不要想当然地读写：你的每一次输出，评测机都会实时接收。因此必须通过 endl 或 fflush(stdout) 清空输出缓冲区。
2. 运算时间不值钱，查询次数是无价之宝：交互题的时间复杂度通常极小（$N \le 26$），我们要竭尽全力优化的是查询次数（也就是信息的获取量）。

下面我将带你从最朴素的暴力版本，一步步进阶到能够通过所有测试点的满分最优版本。所有的代码都严格遵循 NOIP C++14 竞赛标准。

版本一：基础冒泡排序（仅过 Testset 1）

目标：$N=26, Q=1000$。 思路：这个测试点给了足足 1000 次查询。26个元素冒泡排序最坏需要 $\frac{26 \times 25}{2} = 325$ 次比较，绰绰有余。这个版本主要用来让你熟悉交互题的代码结构。

/**
 * 版本一：冒泡排序版
 * 适用范围：Testset 1 (N=26, Q=1000)
 * 预期得分：100 / 300
 */
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// 封装一个查询函数，屏蔽底层交互细节，让主逻辑更清晰
// 返回 true 表示 x < y（即 x 的重量轻于 y）
bool query(char x, char y) {
    // 关键点 1：输出询问格式，并使用 endl 自动刷新缓冲区 (flush)
    cout << "? " << x << " " << y << endl;
    
    char ans;
    cin >> ans; // 读取评测机的实时反馈
    
    // 如果系统返回 '<'，说明 y 比 x 重，即 x < y
    return ans == '<';
}

int main() {
    // 优化 C++ 的 IO 速度（交互题通常不需要，但写上是个好习惯，注意不要和 scanf 混用）
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    if (!(cin >> n >> q)) return 0;

    // 初始化字符串为 "ABCDEFGHIJKLMNOPQRSTUVWXYZ" 的前 N 个字符
    string s = "";
    for (int i = 0; i < n; ++i) {
        s += char('A' + i);
    }

    // 经典冒泡排序
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - 1 - i; ++j) {
            // 易错点 1：如果要升序排列，当 s[j] > s[j+1] 时我们需要交换
            // query 返回 true 是小于，所以加上 '!' 表示大于（或等于，虽然题目保证重量不同）
            if (!query(s[j], s[j + 1])) {
                swap(s[j], s[j + 1]);
            }
        }
    }

    // 最终输出答案，并刷新缓冲区
    cout << "! " << s << endl;

    return 0;
}

版本二：二分插入排序（可过 Testset 1 & 2）

目标：$N=26, Q=100$。 思路：$Q$ 骤减到 100，冒泡排序失效。我们需要用 $O(N \log N)$ 级别的排序。 对于 26 个元素，二分插入排序（Binary Insertion Sort） 的最坏比较次数恰好为： $1 + 2 + 2 + 3 + 3 + 3 + 3 + 4 \times 8 + 5 \times 10 = 99$ 次，完美卡在 100 次以内。

/**
 * 版本二：二分插入排序版
 * 适用范围：Testset 1 & 2 (N=26, Q=100)
 * 预期得分：200 / 300
 */
#include <iostream>
#include <string>

using namespace std;

bool query(char x, char y) {
    cout << "? " << x << " " << y << endl;
    char ans;
    cin >> ans;
    return ans == '<';
}

int main() {
    int n, q;
    if (!(cin >> n >> q)) return 0;

    string s = "A"; // 初始状态只放第一个元素，认为它已有序

    // 从第二个元素（'B'）开始，依次将后续元素“二分插入”到已排好序的字符串 s 中
    for (int i = 1; i < n; ++i) {
        char target = char('A' + i);
        
        // 在已排序的序列 s 中进行二分查找，寻找 target 应该插入的位置
        int l = 0, r = s.length() - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            // 拿待插入元素 target 和中间元素 s[mid] 比较
            if (query(target, s[mid])) {
                // target 比较轻，应该插在左半边
                r = mid - 1;
            } else {
                // target 比较重，应该插在右半边
                l = mid + 1;
            }
        }
        
        // 关键点 2：二分结束时，l 的值就是 target 应当插入的正确索引
        // string 的 insert() 可以在指定位置插入字符
        s.insert(s.begin() + l, target);
    }

    cout << "! " << s << endl;

    return 0;
}

(教练注：如果你用这个代码跑 $N=5$, $Q=7$，最坏需要 8 次，依然会 WA 掉最后一个测试点。)

版本三：满分最优版本（包含福特-约翰逊算法核心）

目标：通过所有测试点（涵盖 $N=5, Q=7$ 极限情况）。 思路：将代码分为两大模块：

1. 当 $N=26$ 时，走常规的二分插入排序流程（最多 99 次）。
2. 当 $N=5$ 时，走福特-约翰逊排序法的特判流程（严格保证 7 次，见前文草稿纸推演部分）。

/**
 * 版本三：终极 AC 版 (结合二分插入与福特-约翰逊特判)
 * 适用范围：所有 Testsets
 * 预期得分：300 / 300
 */
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 交互查询函数
bool query(char x, char y) {
    cout << "? " << x << " " << y << endl;
    char ans;
    cin >> ans;
    return ans == '<';
}

// 解决 N=26 的情况（使用二分插入排序）
void solve_26(int n) {
    string s = "A";
    for (int i = 1; i < n; ++i) {
        char target = char('A' + i);
        int l = 0, r = s.length() - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (query(target, s[mid])) r = mid - 1;
            else l = mid + 1;
        }
        s.insert(s.begin() + l, target);
    }
    cout << "! " << s << endl;
}

// 解决 N=5 的情况（使用精简版福特-约翰逊法，必定只需 7 次询问）
void solve_5() {
    char a = 'A', b = 'B', c = 'C', d = 'D', e = 'E';
    
    // 步骤 1：初步建立大小关系 (消耗 2 次查询)
    if (query(b, a)) swap(a, b); // 确保 a < b
    if (query(d, c)) swap(c, d); // 确保 c < d
    
    // 步骤 2：比较两个胜者，确立主链 (消耗 1 次查询，累计 3 次)
    if (query(d, b)) {
        swap(a, c);
        swap(b, d);
    } 
    // 此时主链关系必定是：a < b < d，且已知 c < d
    
    vector<char> v = {a, b, d}; // 初始化有序主链

    // 步骤 3：将剩下的独立元素 e 二分插入到主链 {a,b,d} 中 (消耗 2 次查询，累计 5 次)
    // 根据二分逻辑手动展开（在 3 个元素中找位置恰好 2 次）
    if (query(e, v[1])) {
        if (query(e, v[0])) v.insert(v.begin(), e);
        else v.insert(v.begin() + 1, e);
    } else {
        if (query(e, v[2])) v.insert(v.begin() + 2, e);
        else v.push_back(e);
    }

    // 步骤 4：将 c 插入（消耗 2 次查询，累计 7 次完成绝杀！）
    // 此时 c 只需要与 d 前面的元素比较。我们需要先找到 d 现在处于哪个位置
    int d_idx = 0;
    for (int i = 0; i < (int)v.size(); ++i) {
        if (v[i] == d) d_idx = i;
    }
    
    // c 严格小于 d，因此只需要在 v[0 ... d_idx-1] 中寻找插入点
    // 这里的区间大小只有 2 个或 3 个元素，二分查找必定在 2 次以内完成
    int l = 0, r = d_idx - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (query(c, v[mid])) r = mid - 1;
        else l = mid + 1;
    }
    v.insert(v.begin() + l, c);

    // 拼接最终答案
    string ans = "";
    for (char x : v) ans += x;
    cout << "! " << ans << endl;
}

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

    int n, q;
    if (!(cin >> n >> q)) return 0;

    // 根据数据范围进行算法分支
    if (n == 5) {
        solve_5();
    } else {
        solve_26(n);
    }

    return 0;
}

复杂度分析与优化建议（教练寄语）

• 查询复杂度（重点）：
  • 交互题中，“查询复杂度”即向评测机发问的次数。版本三中，$N=26$ 时的查询复杂度为严格的 $\sum_{i=1}^{N-1} \lceil \log_2(i+1) \rceil$，上界为 99 次；$N=5$ 时为 $O(1)$ 的固定常数 7 次。满足题目所有的苛刻要求。
• 时间复杂度（Time Complexity）：
  • 版本一的时间复杂度为 $O(N^2)$。
  • 版本三中，找插入位置由于是二分查找，需要 $O(N \log N)$ 的时间；但是由于我们采用了 string::insert / vector::insert，底层数组的位移操作需要 $O(N)$。因此总体运行时间复杂度实质上也是 $O(N^2)$。
• 空间复杂度（Space Complexity）：
  • 使用了一个长度最长为 26 的 string 和 vector，加上递归/栈空间的极小开销，空间复杂度为 $O(N)$，消耗内存不到 1 KB，完美符合 1024 MiB 的限制。
• 时间复杂度优化建议（拓展思考）：
  • 在常规的数据结构与算法题中，如果你想让“基于比较的排序”的执行时间达到严格的 $O(N \log N)$，使用底层基于数组元素的 vector::insert 是不可取的。你应当使用归并排序（Merge Sort）。
  • 然而，归并排序的最坏比较次数上界通常比二分插入排序略差（虽然本题 $N=26$ 时归并也是安全的，但不具有普遍性）。
  • 本题的特殊性在于 $N \le 26$，这意味着 $N^2$ 级别的位移操作最多不过是几百次，这对于现代 CPU（每秒亿级运算）来说连九牛一毛都算不上。所以在这个场景下，保证比较次数最小化才是第一顺位，执行时间的常数级退化完全可以被容忍。这就是针对不同场景灵活变通的工程思维。