Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define all(x) (x).begin(),(x).end()
- using namespace std;
- using ll = long long;
- const int N = 100100;
- struct Edge {
- int to, type;
- };
- int type[N];
- const int A = 1;
- const int B = 2;
- vector<Edge> g[N];
- int color[N];
- void PaintDfs(int from, int clr) {
- color[from] = clr;
- for (auto& [to, tp] : g[from]) {
- if (!color[to]) {
- PaintDfs(to, clr);
- }
- }
- }
- void Dfs2(int from) {
- for (auto& [to, tp] : g[from]) {
- if (type[from] == 0 && type[to] == 0) {
- type[from] = tp;
- type[to] = tp;
- Dfs2(to);
- } else if (type[to] == 0) {
- Dfs2(to);
- }
- }
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int n, a, b;
- cin >> n >> a >> b;
- vector<int> p(n, 0);
- set<int> values;
- for (int i = 0; i < n; i++) {
- cin >> p[i];
- values.insert(p[i]);
- }
- int itr = 0;
- map<int,int> mp, rev;
- for (auto& val : values) {
- mp[val] = itr;
- rev[itr++] = val;
- }
- set<pair<int,int>> st;
- map<int, int> get;
- for (int i = 0; i < n; i++) {
- if (!values.count(a - p[i]) && !values.count(b - p[i])) {
- cout << "NO\n";
- return 0;
- }
- if (values.count(a - p[i])) {
- g[mp[p[i]]].push_back(Edge{mp[a - p[i]], A});
- }
- if (values.count(b - p[i])) {
- g[mp[p[i]]].push_back(Edge{mp[b - p[i]], B});
- }
- st.insert({g[mp[p[i]]].size(), mp[p[i]]});
- p[i] = mp[p[i]];
- get[p[i]] = g[p[i]].size();
- st.insert({get[p[i]], p[i]});
- }
- while (st.size() && st.begin()->first <= 1) {
- auto [q, from] = *st.begin();
- st.erase(st.begin());
- if (type[from]) {
- continue;
- }
- for (auto [to, tp] : g[from]) {
- if (type[to] == 0) {
- type[from] = tp;
- type[to] = tp;
- st.erase({get[to], to});
- for (auto& [to2, tp2] : g[to]) {
- st.insert({--get[to2], to2});
- }
- }
- }
- }
- int clr = 1;
- for (int i = 0; i < n; i++) {
- if (type[i] == 0 && color[i] == 0) {
- PaintDfs(i, clr++);
- }
- }
- vector<vector<int>> vertexes(clr);
- for (int i = 0; i < n; i++) {
- if (type[i] == 0) {
- vertexes[color[i]].push_back(i);
- }
- }
- for (int i = 1; i < clr; i++) {
- bool isChain = false;
- int start = -1;
- for (int vertex : vertexes[i]) {
- for (auto& [to, tp] : g[vertex]) {
- if (to == vertex) {
- isChain = true;
- start = vertex;
- }
- }
- }
- if (isChain) {
- Dfs2(start);
- } else if (vertexes[i].size() & 1) {
- cout << "NO\n";
- return 0;
- } else {
- Dfs2(vertexes[i][0]);
- }
- }
- cout << "YES" << endl;
- for (int i = 0; i < n; i++) {
- cout << type[p[i]] - 1 << " ";
- }
- cout << endl;
- }
Add Comment
Please, Sign In to add comment