题解：P11490 [BalticOI 2023] Staring Contest

zzzyyyyhhhhh · 2025-01-04 19:49:14 · 题解

怎么没题解呢，那就发一篇吧。

首先考虑有 3 个位置，标号为 a,b,c，两两询问得到 x=\min\{a,b\},y=\min\{a,c\},z=\min\{b,c\}。x,y,z 三个值中一定有两个相等，且这个值是三数中最小的数。又因为所有值互不相等，所以可以确定最小值的位置（例如如果 x=y 那么最小值位置在 a 处）。

现在有前缀最大值 a 和次大值 b 和 \min\{a,b\}，每次新加入一个 c 就可以通过两次询问确定一个值。

但是这样的构造操作次数是 2\times n-1 的，无法通过。考虑丧失了哪些性质。对于某些 c 不需要询问两次，如果询问得到的结果 x 小于前缀次大值，那么三数中最小值是 x 且位置在 c。

所以现在次数为 O(n+\texttt{前缀次大值个数})。序列前缀最大值个数期望是 \ln n，那么前缀次大值期望个数小于 2\times \ln n（期望 \ln n 个数更新前缀最大值时次大值被更新，又期望 \ln n 个数可能更新次大值），可以通过本题。

注意要打乱序列。

#include<bits/stdc++.h>
using namespace std;
const int N = 2000;
int n,a[N],ans[N];
inline int ask(int x,int y)
{
    int tmp;
    cout<<"? "<<x<<' '<<y<<endl;
    cin>>tmp;
    return tmp;
}
int x,y,xx,yy,zz;
bool t;
inline void work(int z)
{
    yy=ask(x,z);
    if(yy<xx)
    {
        ans[z]=yy;
        return;
    }
    zz=ask(y,z);
    if(xx==yy)
        ans[x]=xx,x=z,xx=zz;
    else if(yy==zz)
        ans[z]=yy;
    else//xx==zz
        ans[y]=xx,y=z,xx=yy;
}
mt19937 rd(time(0));
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)a[i]=i;
    if(n==2)
    {
        int tmp=ask(1,2);
        ans[1]=ans[2]=tmp;
    }
    else
    {
        shuffle(a+1,a+1+n,rd);
        x=a[1],y=a[2];
        xx=ask(a[1],a[2]);
        for(int i=3;i<=n;i++)
            work(a[i]);
        int tmp=max({xx,yy,zz});
        ans[x]=ans[y]=tmp;
    }
    cout<<"! ";
    for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
    cout<<endl;
}