给你a,b和n个数p[i],问你如何分配这n个数给A,B集合,而且知足:
若x在集合A中,则a-x必须也在集合A中。
若x在集合B中,则b-x必须也在集合B中。ios
第一行 三个数 n a b 1<=n<=1e5 1<=a,b<=1e9
第二行 n个数 p1 p2 p3…pn 1<=pi<=1e9web
若是能够刚好分开就输出第一行 YES
而后第二行输出 n个数 分别表明pi 是哪一个集合的 0 表明是A集合 1表明是B 集合
不行就输出NO
放在哪一个集合均可以的时候优先放Bsvg
4 5 9
2 3 4 5spa
YES
0 0 1 1code
3 3 4
1 2 4xml
NOtoken
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<map> using namespace std; const int maxn=1e5+50; int n,a,b,vis[maxn],f[maxn]; map<int,int> flag; int find(int x) { if(vis[x]==x){ return x; } else{ vis[x]=find(vis[x]); return vis[x]; } } void merge(int a,int b) { int p=find(a); int q=find(b); if(p==q){ return ; } else{ vis[q]=p; return ; } } int main() { cin>>n>>a>>b; int mx=0; for(int i=1;i<=n;i++){ cin>>f[i]; flag[f[i]]=i; mx=max(mx,f[i]); } if(mx>=max(a,b)){ cout<<"NO"<<endl; } else{ for(int i=0;i<=n+1;i++){ vis[i]=i; } for(int i=1;i<=n;i++){ if(flag[a-f[i]]){ merge(i,flag[a-f[i]]); } else{ merge(n+1,i); } if(flag[b-f[i]]){ merge(i,flag[b-f[i]]); } else{ merge(0,i); } } int A=find(0); int B=find(n+1); if(A!=B){ cout<<"YES"<<endl; for(int i=1;i<=n;i++){ if(i!=1){ cout<<" "; } if(find(i)==A){ cout<<"0"; } else{ cout<<"1"; } } cout<<endl; } else{ cout<<"NO"<<endl; } } return 0; }