配点 : 300 点
問題文
这是一个交互式题目的示例。请注意,这不是面向初学者的问题。
初学者请AtCoder 初学者精选尝试挑战一下!
第一个 N 个带有大写字母标签的 N 个球。 任意两个球的重量都不同。
你 您可以在 Q 次查询。 在每次查询中,您可以比较两个球的重量。(详情请参见输入输出部分)
请按重量从轻到重对球进行排序。
制約
- (N, Q) = (26, 1000), (26, 100), (5, 7) 中的任意一种。
部分点
有三个测试集。每组包含 100 个点。
- 特塞特 1: N = 26, Q = 1000
- 特斯托塞托 2: N = 26, Q = 100
- 3: N = 5, Q = 7
入出力
首先,从标准输入中读取 N 和 Q ,其格式如下:
N Q
接下来,您可以进行 Q 次查询。 每次查询都必须按以下格式输出到标准输出:
? c_1 c_2
这里 c_1 和 c_2 必须是不同的前 N 个大写字母中的任意一个。
然后,从标准输入中按以下格式读取查询的答案:
ans
这里 ans 是 < 或 > 。
当
< 当 c_2 较重时,> 当 c_1 较重。
最后,必须按以下格式输出答案:
! ans
这里 ans 是 N 个字符组成的字符串,并且必须是前 N 个大写字母按重量从轻到重排列后的结果。
评测器
- 输出后,必须刷新标准输出。 否则
TLE有可能会发生。 - 输出答案后,必须立即结束程序。否则,其行为未定义。
- 输出的答案错误时,其行为未定义(
WA不一定)。
代码示例
以下代码是使用 C++ 100 获得分数的示例。这是一个可以获得部分分数的代码,因此提交后会得到 WA。
#include <cstdio>
#include <string>
using namespace std;
int main(void){
int N,Q,i,j;
scanf("%d%d", &N, &Q);
string s;
for(i=0;i<N;i++) s += (char)('A' + i);
for(i=0;i<N;i++) for(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;
}