CF1918E ace5 and Task Order
题意
给定一个 1 到 n 的排列 a,初始时交互库随机一个 x∈[1,n]。
现在你可以进行不超过 40n 次查询,每次查询输出 ? i,回答为:
- 如果 ai>x,返回
>,并将 x←x+1。 - 如果 ai<x,返回
<,并将 x←x−1。 - 如果 ai=x,返回
=,x 保持不变。
请你求出 a。
多组测试数据。
数据范围: 1≤T≤1000,1≤∑n≤2000,1≤ai≤n。
题解
有两种做法,随机化和非随机。
随机化做法
这个做法的想法来源于快速排序,每次随机选择一个基准,将小的放左边,大的放右边。
由此,我们维护一个数组 v,里面放着当前排名区间 [l,r] 的元素在 a 中的下标。
每次我们随机一个基准下标 p,通过最多 n 次操作,使 x=v[p]。
然后我们对于其余下标进行一次操作,将小于 x 的放左边,大于的放右边。
由于进行一次操作会导致 x 的变化,考虑在每次操作完其余下标后对 v[p] 进行一次操作,这样就能重新让 x=v[p]。
总询问次数大约 3nlogn≈33n,可以通过。
代码
随机化做法
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <random>
#include <vector>
using namespace std;
const int N = 2010;
int n;
int ans[N];
mt19937 rng;
int query(int x) {
printf("? %d\n" , x); fflush(stdout);
char c[3]; scanf("%s" , c);
if(*c == '>') return 1;
if(*c == '=') return 0;
return -1;
}
int rd(int l , int r) {
return (rng()%(r-l+1)+r-l+1)%(r-l+1)+l;
}
void solve(int l , int r , vector<int> v) {
if(l > r || v.empty()) return;
if(l == r) {
for(auto i : v) ans[i] = l;
return;
}
int ran = rd(0,v.size()-1) , p = v[ran];
while(query(p) != 0);
vector<int> vl , vr;
for(int i = 0 ; i < (int) v.size() ; i ++) {
if(i == ran) continue;
int st = query(v[i]);
if(st == -1) vl.push_back(v[i]);
else vr.push_back(v[i]);
query(p);
}
ans[p] = l+vl.size();
solve(l , l+vl.size()-1 , vl);
solve(l+vl.size()+1 , r , vr);
}
void solve() {
scanf("%d" , &n);
vector<int> vec;
for(int i = 1 ; i <= n ; i ++)
vec.push_back(i);
solve(1 , n , vec);
putchar('!');
for(int i = 1 ; i <= n ; i ++)
printf(" %d" , ans[i]);
puts("");
fflush(stdout);
}
int main() {
rng = mt19937(random_device{}());
int T; scanf("%d" , &T);
while(T --) solve();
return 0;
}