Subtask 1

Với mỗi ~1\le i<n~, ta hỏi hai hoán vị ~P~ và ~Q~ sao cho ~P_0=1,P_i=N~ và ~Q_0=N,Q_i=1~ đồng thời các vị trí còn lại bằng nhau. Ta nhận được hai tổng ~X_0-X_i+C~ và ~X_i-X_0+C~, từ đây ta tính được hiệu ~X_i-X_0~. Để ý rằng khi ~X_i=1~ thì hiệu này đạt giá trị nhỏ nhất, ta tính được ~X_0~ và từ đó dễ dàng khôi phục được hoán vị.</p>

Subtask 2

Ở subtask 1 ta chỉ mới sử dụng giá trị ~1~ và ~N~, để giảm số câu hỏi ta sẽ sử dụng thêm giá trị ~2~. Và để phá được dấu giá trị tuyệt đối thì ta chỉ nên đặt ~2~ vào các vị trí mà ta đã biết nó lớn hơn ~1~.

Xét ba vị trí ~i, j, k~ với điều kiện ta đã biết ~X_i>1~. Ta hỏi hai hoán vị ~P~ và ~Q~ sao cho ~P_i=2,P_j=1,P_k=N~ và ~Q_i=2,Q_j=N,Q_k=1~. Ta nhận được hai tổng ~X_i+X_j-X_k+C~ và ~X_i-X_j+X_k+C~, tính hiệu ~X_j-X_i~ và xác định vị trí lớn hơn, giả sử đó là ~j~. Ta hỏi tiếp hoán vị ~R~ sao cho ~R_i=N,R_j=2,R_k=1~ và nhận được tổng ~-X_i+X_j+X_k+C~. Từ đây dễ dàng tìm được ~X_k-X_i~. Trường hợp ~k~ là chỉ số lớn hơn ta xử lý tương tự.

Trở lại với bài toán, đầu tiên ta tìm hiệu ~X_1-X_0~ và xác định vị trí chắc chắn lớn hơn ~1~. Sau đó cứ mỗi hai phần tử liên tiếp ta áp dụng thuật toán trên và thu được các hiệu, từ đó sử dụng nhận xét ở cuối subtask 1 để khôi phục hoán vị.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

const int N = 505;

int a[N], b[N], p[N], n;

int ask() {
  cout << "ask";
  for (int i = 0; i < n; i++)
    cout << ' ' << p[i];
  cout << endl;
  int res = 0; cin >> res;
  // for (int i = 0; i < n; i++)
    // res += abs(b[i] - p[i]);
  return res;
}

void ask_two(int x, int y) {
  memset(p, 0, sizeof p);
  p[x] = 1; p[y] = n;
  for (int i = 0, j = 2; i < n; i++)
    if (!p[i]) p[i] = j++;
  int pre = ask();
  swap(p[x], p[y]);
  int nex = ask();
  a[y] = (nex - pre) / 2;
}

void ask_three(int x, int y, int z) {
  memset(p, 0, sizeof p);
  p[x] = 2; p[y] = 1; p[z] = n;
  for (int i = 0, j = 3; i < n; i++)
    if (!p[i]) p[i] = j++;
  int pre = ask();
  swap(p[y], p[z]);
  int nex = ask();
  a[y] = (nex - pre) / 2;
  if (a[y] > 0) {
    p[x] = n; p[y] = 1; p[z] = 2;
  } else {
    p[x] = n; p[y] = 2; p[z] = 1;
  }
  nex = ask();
  a[z] = (nex - pre) / 2;
  a[y] = a[z] - a[y];
}

void answer() {
  cout << "answer";
  for (int i = 0; i < n; i++)
    cout << ' ' << a[i];
  cout << endl;
}

int main() {
  int test, U; cin >> test;
  while (test--) {
    cin >> n >> U;
    // for (int i = 0; i < n; i++)
      // cin >> b[i];
    memset(a, 0, sizeof a);
    ask_two(0, 1);
    int t = 0;
    if (a[1] > 0) {
      a[0] = -a[1]; a[1] = 0; t = 1;
    }
    for (int i = 2; i < n; i += 2) {
      if (i == n - 1) ask_two(t, i);
      else ask_three(t, i, i + 1);
    }
    int mn = 0;
    for (int i = 0; i < n; i++)
      mn = min(mn, a[i]);
    for (int i = 0; i < n; i++)
      a[i] -= mn - 1;
    answer();
  }
}