在知乎內查看

題目

思路來源

題解

首先特判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，看詢問出的答案：

1. 如果為0，說明都詢問錯了，則交換u、v所在位置，放進對應vector
2. 如果為2，說明都詢問對了，直接放入對應vector
3. 否則為1，說明u和v位于一邊，此時將v塞進del這個vector里，將u和v在并查集上合并，并把u塞回x

重復這個過程，直至x為空或只剩一個元素，

只剩一個元素時，L或R一定已經有元素，

和已經被詢問出來的元素再一起詢問一次，就能確定出這個元素該放進L還是R

代碼中用to數(shù)組記錄了是放進左邊還是放進右邊，

這樣del里的元素，在并查集上找到其祖先時，可以用to數(shù)組確定其應該被放進L還是R

期望次數(shù)是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