中国老区建设促进会网站,网站制作产品优化,wordpress 头像打岔,wordpress最新中文版在知乎内查看
题目 思路来源 题解
首先特判n1的情况#xff0c;其实也不用问
分治#xff0c;假设当前解决到[l,r]#xff0c;要递归的vector是x#xff0c;
维护两个vector L、R#xff0c;代表下一步要在[l,mid]和[mid1,r]分治的vector
每次将x random_shuffle后1的情况其实也不用问
分治假设当前解决到[l,r]要递归的vector是x
维护两个vector L、R代表下一步要在[l,mid]和[mid1,r]分治的vector
每次将x random_shuffle后取出vector尾部的两个u、v
计分界点为midmid的全填umid的全填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的实际跑得飞快也没被卡掉
代码
#includebits/stdc.h
#includeiostream
#includecstdio
#includevector
#includequeue
#includemap
#includeset
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 pairll,ll P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#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 N1e310;
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,vectorintx){//printf(l:%d r:%d ,l,r);//for(auto v:x)printf(%d ,v);puts();if(lr){ans[l]x[0];return;}for(auto v:x)par[v]v;int mid(lr)/2;vectorintL,R,del;while(SZ(x)1){random_shuffle(x.begin(),x.end());int ux.back();x.pop_back();int vx.back();x.pop_back();rep(i,1,n){if(imid)q[i]u;else q[i]v;}int wask();if(!w)L.pb(v),R.pb(u),to[v]0,to[u]1;else if(w2)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 ux[0];if(SZ(L)){rep(i,1,n){if(imid)q[i]u;else q[i]L[0];}int wask();if(!w)R.pb(u),to[u]1;else L.pb(u),to[u]0;}else if(SZ(R)){rep(i,1,n){if(imid)q[i]R[0];else q[i]u;}int wask();if(!w)L.pb(u),to[u]0;else R.pb(u),to[u]1;}else{assert(false);}}for(auto v:del){int fafind(v);if(!to[fa])L.pb(v);else R.pb(v);}if(SZ(L))sol(l,mid,L);if(SZ(R))sol(mid1,r,R);
}
void sol(){if(n1){ans[1]1;out();return;}vectorintnow;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
