CF468B题解

Ag2WO4 · 2024-08-06 01:18:44 · 题解

前排提示：这其实真的是水题！

考虑根据可放置的集合建图，由于只有两个集合，边最多两条，只能成线或者简单环。对于线，显然偶数长度有解奇数长度无解；而对于简单环的情况，特判即可：

• 若不然，当 x 存在时两步变换可推 x+a-b 存在，此时沿环的一个方向无限前进无法回到 x 本身，推出矛盾。

寻找线的端点（边数小于二），遍历线的长度，最终特判环即可。

a,b,c=map(int,input().split());a={i:-1 for i in map(int,input().split())}
for i in a:
    if-1==a[i]:
        if b-i not in a or c-i not in a:
            d=i;e=f=0
            if b-i not in a:f=1
            while 1:
                a[d]=f
                if e:
                    if f:
                        if b-d not in a:break
                    elif c-d not in a:break
                else:
                    if f:
                        if c-d not in a:print('NO');exit()
                    elif b-d not in a:print('NO');exit()
                d=c-d if e^f else b-d;e^=1
print('YES');print(*(abs(a[i])for i in a))