The 2024 ICPC Kunming Invitational Contest K. Permutation（交互 期望）
在知乎内查看
题目
思路来源
题解
首先特判n=1的情况，其实也不用问
分治，假设当前解决到[l,r]，要递归的vector是x，
维护两个vector L、R，代表下一步要在[l,mid]和[mid+1,r]分治的vector
每次将x random_shuffle后，取出vector尾部的两个u、v，
计分界点为mid，<=mid的全填u，>mid的全填v，看询问出的答案：
- 如果为0，说明都询问错了，则交换u、v所在位置，放进对应vector
- 如果为2，说明都询问对了，直接放入对应vector
- 否则为1，说明u和v位于一边，此时将v塞进del这个vector里，将u和v在并查集上合并，并把u塞回x
重复这个过程，直至x为空或只剩一个元素，
只剩一个元素时，L或R一定已经有元素，
和已经被询问出来的元素再一起询问一次，就能确定出这个元素该放进L还是R
代码中用to数组记录了是放进左边还是放进右边，
这样del里的元素，在并查集上找到其祖先时，可以用to数组确定其应该被放进L还是R
期望次数是6000的，实际跑得飞快，也没被卡掉
代码
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e3+10;
int n,ans[N],q[N],par[N],to[N];
int find(int x){
return par[x]==x?x:par[x]=find(par[x]);
}
int ask(){
printf("0");
rep(i,1,n){
printf(" %d",q[i]);
}
printf("\n");
fflush(stdout);
int v;
sci(v);
return v;
}
void out(){
printf("1");
rep(i,1,n){
printf(" %d",ans[i]);
}
printf("\n");
fflush(stdout);
}
void sol(int l,int r,vector<int>x){
//printf("l:%d r:%d ",l,r);
//for(auto &v:x)printf("%d ",v);puts("");
if(l==r){
ans[l]=x[0];
return;
}
for(auto &v:x)par[v]=v;
int mid=(l+r)/2;
vector<int>L,R,del;
while(SZ(x)>1){
random_shuffle(x.begin(),x.end());
int u=x.back();x.pop_back();
int v=x.back();x.pop_back();
rep(i,1,n){
if(i<=mid)q[i]=u;
else q[i]=v;
}
int w=ask();
if(!w)L.pb(v),R.pb(u),to[v]=0,to[u]=1;
else if(w==2)L.pb(u),R.pb(v),to[u]=0,to[v]=1;
else del.pb(v),x.pb(u),par[v]=u;
}
//printf("x:%d L:%d R:%d\n",SZ(x),SZ(L),SZ(R));
if(SZ(x)==1){
int u=x[0];
if(SZ(L)){
rep(i,1,n){
if(i<=mid)q[i]=u;
else q[i]=L[0];
}
int w=ask();
if(!w)R.pb(u),to[u]=1;
else L.pb(u),to[u]=0;
}
else if(SZ(R)){
rep(i,1,n){
if(i<=mid)q[i]=R[0];
else q[i]=u;
}
int w=ask();
if(!w)L.pb(u),to[u]=0;
else R.pb(u),to[u]=1;
}
else{
assert(false);
}
}
for(auto &v:del){
int fa=find(v);
if(!to[fa])L.pb(v);
else R.pb(v);
}
if(SZ(L))sol(l,mid,L);
if(SZ(R))sol(mid+1,r,R);
}
void sol(){
if(n==1){
ans[1]=1;
out();
return;
}
vector<int>now;
rep(i,1,n)now.pb(i);
sol(1,n,now);
out();
}
int main(){
srand(time(NULL));
sci(n);
sol();
return 0;
}
//2 3 4 1 5
原文地址：https://blog.csdn.net/Code92007/article/details/142748828
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！