Вопрос: http://codeforces.com/contest/468/problem/B
Маленький X имеет n различных целых чисел: p1, p2, ..., pn. Он хочет разделить их все на два множества А и В. Должны быть выполнены следующие два условия:
Если число x принадлежит множеству A, то число a - x также должно принадлежать множеству A. Если число x принадлежит множеству B, то число b - x также должно принадлежать множеству B. Помогите Маленькому X разделить числа на два множества или определить, что это невозможно.
Входные данные В первой строке через пробел записаны три целых числа n, a, b (1 ≤ n ≤ 105; 1 ≤ a, b ≤ 109). В следующей строке через пробел записаны n различных целых чисел p1, p2, ..., pn (1 ≤ pi ≤ 109).
Выходные данные Если есть способ разделить числа на два множества, то в первой строке выведите «YES». Затем выведите n целых чисел: b1, b2, ..., bn (bi равно либо 0, либо 1), описывающих деление. Если bi равно 0, то pi принадлежит множеству A, иначе — множеству B.
Если это невозможно, выведите «NO» (без кавычек).
Теперь я разработал следующий код:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
int n,a,b,id;
int p[100100];
set<int> st;
map<int,int> mp;
int fa[100100];
int find(int x)
{
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
void Bing(int a,int b)
{
int A=find(a),B=find(b);
if(A==B) return ;
fa[B]=A;
}
int main()
{
scanf("%d%d%d",&n,&a,&b);
for(int i=1;i<=n;i++)
{
scanf("%d",p+i);
st.insert(p[i]);
mp[p[i]]=++id;
fa[i]=i;
}
fa[n+1]=n+1;///A
fa[n+2]=n+2;///B
for(int i=1;i<=n;i++)
{
int x=p[i];
int flag = 0;
if(st.count(a-x))
{
Bing(mp[x],mp[a-x]);
flag = 1;
}
else
{
Bing(n+1,mp[x]);
flag = 1;
}
if(st.count(b-x) && flag == 0)
{
Bing(mp[x],mp[b-x]);
}
else if (flag == 0)
{
Bing(n+2,mp[x]);
}
}
if(find(n+1)==find(n+2))
{
puts("NO");
}
else
{
puts("YES");
for(int i=1;i<=n;i++)
{
printf("%d ",find(i)==find(n+1));
}
putchar(10);
}
return 0;
}
По сути, попробуйте объединить каждый элемент либо с набором A, либо с набором B. И затем, наконец, выведите NO, если оба они объединены по очереди. Однако это дает неправильный ответ при вводе:
3 3 4
1 2 4
Вывод должен быть: NO
, тогда как мой код выводит как
YES
0 0 1
Где я ошибаюсь в своей логике? Пожалуйста помоги!
1
и2
оба принадлежатA
, то3-1=2
и3-2=1
тоже принадлежат, а4
и4-4=0
оба могут принадлежать множеству B. Или результат вычитания также должен соответствовать границам? - person Weak to Enuma Elish   schedule 15.11.20150
допустимым результатом. - person Weak to Enuma Elish   schedule 15.11.2015