题目详情题解（0）讨论（0）提交记录（0）

AT_agc010_e.[AGC010E] Rearranging

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

黑板上写有 NN 个整数，第 ii 个整数为 AiA_i。

高桥君和青木君按照以下步骤将这些数排列成一行：

  • 首先，高桥君可以按照自己喜欢的顺序将这些数排成一行。
  • 接着，青木君可以任意多次选择相邻的两个数进行交换，但被交换的两个数必须互质。

假设高桥君总是使最终排列字典序最小，青木君总是使最终排列字典序最大，请你求出最终的数列。

输入格式

输入从标准输入中给出，格式如下：

NN A1A_1 A2A_2 … ANA_N

输出格式

请输出最终的数列，用一行表示。

输入输出样例

  • 输入#1

    5
1 2 3 4 5

    输出#1

    5 3 2 4 1

  • 输入#2

    4
2 3 4 6

    输出#2

    2 4 6 3

说明/提示

限制条件

  • 1≤N≤20001 \leq N \leq 2000
  • 1≤Ai≤1081 \leq A_i \leq 10^8

样例解释 1

高桥君如果将给定的数按 (1,2,3,4,5)(1,2,3,4,5) 的顺序排列，则青木君最优操作后可以变成 (5,3,2,4,1)(5,3,2,4,1)。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页