题解：P14134 【MX-X22-T5】「TPOI-4E」Get MiN? Get MeX!

· · 题解

前言

该做法比较神秘。

Solution

首先设 U 为当前可能成为答案的集合，当 |U|< 6 时可以逐个排除，否则把它平均分成三个集合，设为 P_1,P_2,P_3。

发现 1\notin U 时是简单的，因为 0 所在的那个集合的 \min+\operatorname*{mex} 恒为 1，这样我们就可以通过两次询问 1 来确定三个集合中哪个集合包含 0，也就是 |U|\to \frac{|U|}{3}。

然后考虑 0,1\in U，发现它俩被分到同一个集合 P_i 的概率是 \frac{1}{3}。那么当它俩被分到同一个集合时，会有两个集合的 \min+\operatorname*{mex} 相等，这时候不好区分，那么我们可以把两个集合都保留下来，也就是 |U|\to \frac{2|U|}{3}，这里只需要两次询问 1。否则我们可以用一次询问 2 把包含 1 的那个集合删掉，然后按照 1\notin U 来操作即可。

期望次数我不会算，但是我询问 1 最多只用了 24 次，欢迎大家来 hack。

#include<bits/stdc++.h>
#include<cmath>
#define ll long long
#define ld long double
#define ull unsigned long long
#define lll __int128
#define N 500010
#define For(i,a,b) for(register ll i=a;i<=b;++i)
#define Rof(i,a,b) for(register ll i=a;i>=b;--i)
#define ls x<<1
#define rs x<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define mk make_pair
#define pb emplace_back
#define pii pair<ll,ll>
#define pque priority_queue
#define fi first
#define se second

using namespace std;
int a[N];
vector<int >now,p[3];
int n;

inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int ask1(vector<int >y){
    cout<<"? 1 "<<(int)y.size()<<' ';
    for(int i:y) cout<<i<<' ';
    cout<<endl;
    int x=read();
    return x;
}
int ask2(vector<int >y){
    cout<<"? 2 "<<(int)y.size()<<' ';
    for(int i:y) cout<<i<<' ';
    cout<<endl;
    int x=read();
    return x;
}

int main()
{
    //freopen("sort.in","r",stdin);
    //freopen("sort.out","w",stdout);
    n=read();
    For(i,1,n) now.pb(i);
    int is=0;
    while(n>=6){
        For(i,0,2) p[i].clear();
        for(int i=0;i<now.size();++i) p[i%3].pb(now[i]);
        now.clear();
        int q1=ask1(p[0]),q2=ask1(p[1]);
        if(is){
            if(q1==1) now=p[0];
            else if(q2==1) now=p[1];
            else now=p[2];
            n=now.size();
            continue;
        }
        if(q1==q2){
            if(q1==1){
                int q3=ask2(p[0]);
                if(q3<0) now=p[0];
                else now=p[1];
                n=now.size();
                is=1;
                continue;
            }
            for(int i:p[0]) now.pb(i);
            for(int i:p[1]) now.pb(i);
            n=now.size();
        }else if(q1<q2){
            if(q1==1){
                int q3=ask2(p[0]);
                if(q3<0) now=p[0];
                else now=p[2];
                n=now.size();
                is=1;
                continue;
            }
            for(int i:p[0]) now.pb(i);
            for(int i:p[2]) now.pb(i);
            n=now.size();
        }else{
            if(q2==1){
                int q3=ask2(p[1]);
                if(q3<0) now=p[1];
                else now=p[2];
                n=now.size();
                is=1;
                continue;
            }
            for(int i:p[1]) now.pb(i);
            for(int i:p[2]) now.pb(i);
            n=now.size();
        }
    }
    For(i,1,n) a[i]=ask1({now[i-1]});
    int mn=1000000;
    For(i,1,n) mn=min(mn,a[i]);
    int pos1=0,pos2=0;
    For(i,1,n){
        if(a[i]==mn){
            if(!pos1) pos1=now[i-1];
            else pos2=now[i-1];
        }
    }
    if(!pos2){
        cout<<"! "<<pos1<<endl;
        return 0;
    }
    int re=ask2({pos1});
    if(re<0) cout<<"! "<<pos1<<endl;
    else cout<<"! "<<pos2<<endl;
    return 0;
}
/*

*/