题目描述

在一家拉面餐厅里有 $N$ 个朋友 $F_0,F_1,\ldots,F_{N-1}$ 和 $N$ 种拉面 $R_0,R_1,\ldots,R_{N-1}$。

朋友 $F_i$ 对拉面 $R_j$ 有一个喜好值 $A_{i,j}$。喜好值越大，表示朋友越喜欢这种拉面。对于同一个朋友，他对不同拉面的喜好值两两不同；也就是说，当 $j\ne j'$ 时，必有 $A_{i,j}\ne A_{i,j'}$。喜好值可以为负数。

朋友们会多次光顾这家餐厅。每次光顾时，因为每种拉面只能被一个朋友选择，所以任何两个朋友不能选择同一种拉面。

一次光顾时，你可以指定朋友们进入餐厅的顺序，即一个 $0,1,\ldots,N-1$ 的排列

朋友们会按照这个顺序依次选择拉面：

• 第一个朋友 $F_{\pi_0}$ 会选择自己最喜欢的拉面；
• 第二个朋友 $F_{\pi_1}$ 会在剩下的拉面中选择自己最喜欢的；
• 依此类推，朋友 $F_{\pi_i}$ 会在前面朋友尚未选择的拉面中选择自己最喜欢的。

若在某个顺序下，朋友 $F_i$ 最终选择了拉面 $R_{\sigma_i}$，则该顺序的满意度为

你的任务是找到一个进入顺序，使满意度最大。

交互方式

你需要提交一个 C++ 程序，并包含头文件：

#include "ramen.h"

你只需要实现下面这个函数：

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

其中 $N$ 是朋友数量。函数需要返回一个 $0,1,\ldots,N-1$ 的排列，表示你给出的进入顺序。

在 find_order 中，你可以调用下面的函数进行询问：

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

其中 order 必须是 $0,1,\ldots,N-1$ 的一个排列。交互器会按照这个顺序模拟朋友们选择拉面，并返回一个长度为 $N$ 的数组 ret。

对于每个朋友 $i$，ret[i] = {x, y} 表示朋友 $F_i$ 在这次模拟中选择了拉面 $R_x$，并且对应喜好值为 $y=A_{i,x}$。

调用 query 的次数不得超过测试数据给定的限制。正式数据中该限制为 $750$ 次。

样例说明

设 $N=2$，喜好值矩阵为

一次可能的交互过程如下：

若顺序为 {0,1}，满意度为 $9+0=9$。

若顺序为 {1,0}，满意度为 $5+5=10$。

因此最优顺序是 {1,0}，find_order(2) 应返回 {1,0}。

数据范围

• $1\le N\le 75$；
• $|A_{i,j}|\le 2\,000\,000$；
• 对于任意固定的 $i$，$A_{i,0},A_{i,1},\ldots,A_{i,N-1}$ 两两不同；
• 正式数据中最多允许调用 query $750$ 次。

@头文件下载

提交说明

本题为交互/库题。你提交的代码不需要写 main 函数，评测时提供的 ramen.h 会负责读入 $N$、输出询问与最终答案。

如果你自己写了 main 函数，可能会与评测头文件中的 main 冲突，导致编译错误。