CF1918E ace5 and Task Order

思路

首先，你显然可以用 $3n$ 次操作求出 $a_1$ 和 $x$。同时整个序列可以按照值分为小于 $a_1$ 和大于 $a_1$ 两部分。

考虑分别处理这两个部分。你希望还可以通过分治的方法，将一个部分再分为一个部分。

但是，由于数据的不随机性，我们不能单纯的选取一个部分的第一个当作分界点，因为容易构造一个有单调性的序列，每次分治都只会被分出来一个数。

既然数据不随机，我们就选得随机。每一次随机选取一个数当作一个数，这样我们每一次分治期望情况下是能将序列平均分的。因此询问次数是 $(3 \times \log n) \times n$ 次的。

Code

#include <bits/stdc++.h>
#define re register

using namespace std;

mt19937 rnd(random_device{}());
const int N = 2010;
int n,x,arr[N];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

inline void dfs(vector<int> v,int l,int r){
    if (l == r) return arr[v.back()] = l,void();
    int len = v.size(); int id = abs((int)rnd()) % len;
    vector<int> a,b;
    while (1){
        printf("? %d\n",v[id]); fflush(stdout);
        char op[10]; scanf("%s",op);
        if (op[0] == '<') x--;
        else if (op[0] == '>') x++;
        else break;
    }
    arr[v[id]] = x;
    for (auto p:v){
        if (p == v[id]) continue;
        printf("? %d\n",p); fflush(stdout);
        char op[10]; scanf("%s",op);
        if (op[0] == '<') a.push_back(p);
        else b.push_back(p);
        printf("? %d\n",v[id]); fflush(stdout);
        scanf("%s",op);
    }
    if (!a.empty()) dfs(a,l,x - 1);
    if (!b.empty()) dfs(b,x + 1,r);
}

inline void solve(){
    vector<int> a,b;
    int num = 1;
    n = read();
    while (1){
        puts("? 1"); fflush(stdout);
        char op[10]; scanf("%s",op);
        if (op[0] == '=') break;
    }
    for (re int i = 2;i <= n;i++){
        printf("? %d\n",i); fflush(stdout);
        char op[10]; scanf("%s",op);
        if (op[0] == '<'){
            num++; a.push_back(i);
        }
        else b.push_back(i);
        puts("? 1"); fflush(stdout);
        scanf("%s",op);
    }
    arr[1] = x = num;
    if (!a.empty()) dfs(a,1,num - 1);
    if (!b.empty()) dfs(b,num + 1,n);
    printf("! ");
    for (re int i = 1;i <= n;i++) printf("%d ",arr[i]);
    puts(""); fflush(stdout);
}

int main(){
    int T; T = read();
    while (T--) solve();
    return 0;
}