做题感悟:比赛时做完第三题就关门了,回去想了一下也没想到好的方法,感觉弱爆了。
解题思路:
官方题解:
代码:
#include<iostream> #include<sstream> #include<map> #include<cmath> #include<fstream> #include<queue> #include<vector> #include<sstream> #include<cstring> #include<cstdio> #include<stack> #include<bitset> #include<ctime> #include<string> #include<iomanip> #include<algorithm> using namespace std ; #define INT long long int const int INF = 99999999 ; const double esp = 0.00000001 ; const double PI = acos(-1.0) ; const int MP = 2000000 + 5 ; const int MY = (1<<9) + 5 ; const int MX = 100000 + 5 ; int n ,a ,b ; map<int ,int>m ; int g[MX] ,fa[MX] ; int find(int x) { if(fa[x] != x) fa[x] = find(fa[x]) ; return fa[x] ; } int main() { while(~scanf("%d%d%d" ,&n ,&a ,&b)) { m.clear() ; for(int i = 1 ;i <= n ; ++i) { scanf("%d" ,&g[i]) ; m[g[i]] = i ; } for(int i = 1 ;i <= n+2 ; ++i) fa[i] = i ; for(int i = 1 ;i <= n ; ++i) { if(m[a-g[i]]) fa[find(i)] = find(m[a-g[i]]) ; else fa[find(i)] = find(n+2) ; if(m[b-g[i]]) fa[find(i)] = find(m[b-g[i]]) ; else fa[find(i)] = find(n+1) ; } if(find(n+1) == find(n+2)) cout<<"NO"<<endl ; else { cout<<"YES"<<endl ; for(int i = 1 ;i <= n ; ++i) { if(i != 1) cout<<" " ; cout<<(find(i) == find(n+2)) ; } cout<<endl ; } } return 0 ; }