#5. 慢速排序/交互题测试

内存限制:256 MiB 时间限制:5000 ms 题目类型:交互
上传者: new_user_4

题目描述

请先阅读交互题须知 英文 中文(STDIO交互部分)

t 组数据,每组数据包含一个长度为 n 的隐藏数组。你的任务是通过操作将数组排序为单调不减序列,即对于每对 i < j,需要保证

交互器会首先输出数组的长度 n。你可以通过以下三种操作与交互器进行交互:

  1. 查询操作 c x y

    • 查询数组中第 x 个数与第 y 个数的大小关系。
    • 交互器返回一个字符:
      • 若返回 '>',表示第 x 个数大于第 y 个数。
      • 若返回 '<',表示第 x 个数小于等于第 y 个数。
  2. 交换操作 s x y

    • 交换数组中第 x 个数与第 y 个数。
  3. 完成操作 e

    • 表示排序完成,交互器会检查当前数组是否满足单调不减要求。

输出询问或回答后,不要忘记输出换行并刷新缓存区。否则,您可能会收到 Time limit exceeded 判定。为此,请使用:

在 C++ 中 fflush(stdout)或 cout.flush()

在 Java 中 System.out.flush()

在 Pascal 中 flush(output)

在 Python 中 stdout.flush()

对于其他语言,请参阅其他语言的文档。

你最多可以进行 次操作。

注意事项

  • 若交互器返回 '!',表示你进行了非法操作或者超出了操作次数限制,此时程序应当退出。
  • 若不及时退出,交互器可能会随机返回一种错误。

输入格式

  • 第一行包含一个整数 t,表示数据组数。
  • 对于每组数据:
    • 第一个输入是整数 n,表示数组的长度。

样例

输入 #1

1 

3

<

<

>

输出 #1

c 2 3

c 1 3

c 1 2

s 1 2

e

输入 #2

1 

3

<

>

输出 #2

c 1 2

s 1 2

c 1 3

s 1 3

s 2 3

e

注意:这只是一种可行的操作方式,并不代表唯一解法

样例1中隐藏的数组的一种可能情况为[2,1,3]

样例2中隐藏的数组的一种可能情况为[2,3,2]

数据范围与提示

t=1

n<=200

<=