题目描述

题目译自 Romanian Master of Informatics 2024 Day2 T2 「Ramen」

在一家拉面餐厅里有 $N$ 个朋友 $F_0, \ldots, F_{N-1}$ 和 $N$ 种拉面 $R_0, \ldots, R_{N-1}$。每个朋友 $F_i$ 对每种拉面 $R_j$ 都有一个独特的喜好值 $A_{ij}$——喜好值越大，说明朋友 $F_i$ 越喜欢拉面 $R_j$。每个朋友对不同拉面的喜好值都不相同，也就是说，对于 $j \neq j'$，$A_{ij} \neq A_{ij'}$。当然，喜好值可能是负数，即 $A_{ij} < 0$。

假设这些朋友多次光顾这家拉面餐厅。每次拜访时，由于拉面库存有限，任何两个朋友不能选择同一种拉面。朋友们会按照某个排列顺序 $F_{\pi_0}, \ldots, F_{\pi_{N-1}}$（这是 $0, \ldots, N-1$ 的一个排列）依次挑选拉面。第一个朋友 $F_{\pi_0}$ 会选自己最喜欢的拉面（喜好值最高的）；第二个朋友 $F_{\pi_1}$ 会从剩下的拉面中选自己最喜欢的（除了 $F_{\pi_0}$ 已选的那种），依此类推。也就是说，$F_{\pi_i}$ 会在 $F_{\pi_0}, \ldots, F_{\pi_{i-1}}$ 未选的拉面中挑出自己最喜欢的。

某个排列 $\pi$ 的满意度定义为每个朋友对自己所选拉面喜好值的总和。换句话说，如果朋友 $i$ 选了拉面 $\sigma_i$，那么排列 $\pi$ 的满意度是 $\sum_{i=0}^{N-1} A_{i, \sigma(i)}$。

你的目标是找到一个排列 $\pi$，让满意度最大。你可以通过尝试不同的顺序（也就是模拟多次餐厅拜访）来实现，但要尽量减少拜访次数，找到最优排列。

交互方式

你需要实现以下函数：

std::vector<int> find_order(int N);

这里的 $N$ 是朋友的数量。函数需要返回一个 $0, \ldots, N-1$ 的排列 $\pi$，使得满意度最大。为了实现这个功能，你可以多次调用以下函数，但调用次数不得超过 $750$ 次：

std::vector<std::pair<int, int>> query(const std::vector<int>& order);

这个函数接收一个 $0, \ldots, N-1$ 的排列 $\pi$（通过参数 order 传入），返回一组配对 $(\sigma(i), A_{i, \sigma(i)})$，其中 $\sigma(i)$ 是朋友 $i$ 在给定顺序 $\pi$ 下所选拉面的种类。

样例

在这个样例中，有 $N = 2$ 个朋友，对 $N = 2$ 种拉面的喜好值 $A_{i, j}$ 如下：

交互过程从系统调用你的函数 find_order(2) 开始。你的函数接着查询了两种可能的排列：$\{0, 1\}$ 和 $\{1, 0\}$。排列 $\{0, 1\}$ 的满意度是 $0 + 9 = 9$，而 $\{1, 0\}$ 的满意度是 $5 + 5 = 10$。最后，函数返回了满意度更高的排列 $\{1, 0\}$，这正是题目要求的最优解。

数据范围与提示

• $1 \leq N \leq 75$
• $| A_{ij} | \leq 2 \ 000 \ 000$
• 参考解法需要最多 $cN^k$ 次查询（$c, k \geq 1$ 为常数）。为了不给测试系统造成过大负担，你最多可以调用 query 函数 $750$ 次，这一限制充分考虑了参考解法的实际性能。