AtCoder原题出处

🏷️ B - Interactive Sorting

⏱️ Time Limit: 2.0 sec   |   💾 Memory Limit: 1024 MiB   |   🏅 Score: 300 points

📖 Problem Statement / 题目描述

This is an interactive task. Please note that these are not beginner questions. If you are a beginner, try the AtCoder Beginners Selection!

这是一个交互式任务。请注意，这不是一道入门级问题。如果您是初学者，请尝试 AtCoder Beginners Selection！

There are $N$ balls labeled with the first $N$ uppercase letters. The balls have pairwise distinct weights.

有 $N$ 个球，分别用前 $N$ 个大写字母标记。这些球的重量各不相同。

You are allowed to ask at most $Q$ queries. In each query, you can compare the weights of two balls (see Input/Output section for details). Sort the balls in the ascending order of their weights.

您最多可以进行 $Q$ 次查询。在每次查询中，您可以比较两个球的重量（详见输入/输出部分）。请按重量升序对这些球进行排序。

⚠️ Constraints / 限制条件

• $(N, Q) = (26, 1000)$, or $(26, 100)$, or $(5, 7)$

🎯 Partial Score / 部分分数

There are three testsets. Each testset is worth 100 points. 共有三个测试集。每个测试集独立算分，各占 100 分：

• Testset 1: $N = 26$ 且 $Q = 1000$
• Testset 2: $N = 26$ 且 $Q = 100$
• Testset 3: $N = 5$ 且 $Q = 7$

🔄 Interaction Protocol / 交互格式 (输入与输出)

1. 初始输入

First, you are given $N$ and $Q$ from Standard Input in the following format: 首先，你需要从标准输入中按以下格式读取 $N$ 和 $Q$：

N Q

2. 发起查询

Then, you start asking queries (at most $Q$ times). Each query must be printed to Standard Output in the following format: 然后，你可以开始发起查询（最多 $Q$ 次）。每次查询必须按以下格式输出到标准输出：

? c1 c2

注： 这里 $c_1$ 和 $c_2$ 都必须是前 $N$ 个大写字母之一，且两者必须不同。

3. 获取反馈

Then, you are given the answer to the query from Standard Input in the following format: 接着，系统会通过标准输入返回你查询的结果：

ans

注： ans 是 < 或 >。

• 当 ans 为 < 时，说明球 $c_2$ 比球 $c_1$ 重。
• 当 ans 为 > 时，说明球 $c_1$ 比球 $c_2$ 重。

4. 输出答案

Finally, you must print the answer to Standard Output in the following format: 最后，你必须按以下格式将最终排序结果打印到标准输出：

! ans

注： 这里的 ans 必须是一个长度为 $N$ 的字符串，包含前 $N$ 个大写字母各一次，且必须表示球按重量升序排列的结果。

⚖️ Judgement / 判题须知

1. 刷新缓冲区 (Flush)： After each output, you must flush Standard Output. Otherwise you may get TLE. (每次输出后，必须刷新标准输出。否则可能会得到 TLE。)
2. 立即终止 (Terminate)： After you print the answer, the program must be terminated immediately. (在打印完最终答案后，程序必须立即终止。)
3. 未定义行为 (Undefined Behavior)： When your output is invalid or incorrect, the behavior of the judge is undefined. (当你的输出无效或错误时，评测机的行为是未定义的，不一定会返回 WA。)

💻 Sample Code / 示例代码 (100分部分解)

Here is a sample solution for 100 points (Testset 1). Submitting it will result in a WA for the full problem. 这是一个能拿 100 分（仅通过测试集1）的示例解法。直接提交会导致最终结果为 WA。

#include <cstdio>
#include <string>
#include <iostream>

using namespace std;

int main() {
    int N, Q;
    scanf("%d%d", &N, &Q);

    string s;
    for(int i = 0; i < N; i++) s += (char)('A' + i);

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N - 1; j++){
            printf("? %c %c\n", s[j], s[j+1]);
            fflush(stdout); // 必须刷新缓冲区
            
            char ans;
            scanf(" %c", &ans);
            if(ans == '>') swap(s[j], s[j+1]);
        }
    }

    printf("! %s\n", s.c_str());
    fflush(stdout);

    return 0;
}

📝 Sample Interaction / 交互示例

In this sample $N=3$, $Q=10$, and the true answer is BAC. 在此示例中，假设 $N=3$， $Q=10$，且真实的重量升序为 BAC。