← 返回题目列表

AtCoder · practice_2

B. 交互式排序

中文机器翻译题面 查看原题

配点 : 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;
}