专栏文章

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

ggcx12012
P14134题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minpvxrn
此快照首次捕获于
2025/12/02 06:24
3 个月前
此快照最后确认于
2025/12/02 06:24
3 个月前
查看原文

前言

该做法比较神秘。

Solution

首先设 UU 为当前可能成为答案的集合，当 ∣U∣<6|U|< 6 时可以逐个排除，否则把它平均分成三个集合，设为 P1,P2,P3P_1,P_2,P_3。
发现 1∉U1\notin U 时是简单的，因为 00 所在的那个集合的 min⁡+mex⁡\min+\operatorname*{mex} 恒为 11，这样我们就可以通过两次询问 11 来确定三个集合中哪个集合包含 00，也就是 ∣U∣→∣U∣3|U|\to \frac{|U|}{3}。
然后考虑 0,1∈U0,1\in U，发现它俩被分到同一个集合 PiP_i 的概率是 13\frac{1}{3}。那么当它俩被分到同一个集合时，会有两个集合的 min⁡+mex⁡\min+\operatorname*{mex} 相等，这时候不好区分，那么我们可以把两个集合都保留下来，也就是 ∣U∣→2∣U∣3|U|\to \frac{2|U|}{3}，这里只需要两次询问 11。否则我们可以用一次询问 22 把包含 11 的那个集合删掉，然后按照 1∉U1\notin U 来操作即可。
期望次数我不会算，但是我询问 11 最多只用了 2424 次，欢迎大家来 hack。
CPP
#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;
}
/*

*/

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...