UOJ Logo Universal Online Judge

UOJ

#750. 【UNR #6】小火车

附件下载 统计

hehe 蚤在下山市发现了当地特色的玩具小火车!

hehe 蚤立马迫不及待的开始玩了起来。小火车运行在一个长度为 $p$ 的圆形铁轨上。小火车上有 $n$ 个拨杆,把第 $i$ 个拨杆向左拨可以让小火车向前开 $a_i$ 单位距离,而向右拨可以让小火车向后开相同距离。每个拨杆最多被拨一次。

hehe 蚤想让小火车开回原位,他想让你告诉他,该怎么拨拨杆才能让小火车运行后回到原位。你不必拨每一个拨杆,但不能一个拨杆都不拨,否则就不好玩了。

显然拨杆的顺序并不会影响最后火车的位置,所以你只需要输出每个拨杆的拨法。

一句话题意:给定 $n,p$ 和长度为 $n$ 的整数序列 $a$,你需要输出整数序列 $b$ 满足:

  1. $b_i\in \{-1,0,1\}$ 且不全为 $0$。

  2. $\sum a_ib_i\equiv 0\pmod p$

保证 $2^n\gt p$

输入格式

第一行两个整数 $n,p$ 表示集合大小和模数。

第二行 $n$ 个整数 $a_i$ 表示集合内容。

输出格式

若无解输出 IMPOSSIBLE

否则输出一行 $n$ 个 $-1$ 到 $1$ 的整数,第 $i$ 个整数为 $-1$ 表示第 $i$ 个拨杆向左拨,$1$ 表示第 $i$ 个拨杆向右拨,$0$ 表示第 $i$ 个拨杆将不会被操作。

如有多组解输出任意一组均可。

样例一

input

3 7
1 2 3

output

1 1 -1

explanation

小火车会向后开 $1+2=3$ 单位距离,向前开 $3$ 单位距离,回到原位。

样例二

见附件下载中的 ex_train2.inex_train2.ans

数据范围

子任务编号 $n\leq$ 特殊性质 分值
$1$ $15$ $20$
$2$ $20$ $20$
$3$ $36$ 数据随机 $20$
$4$ $40$ $40$

数据随机是指:$a_i$ 在 $[0,p)$ 范围内独立均匀随机。

第 $3$ 个子任务有 $5$ 组测试数据。

对于所有数据,保证 $1\leq p\lt 2^n, 1\leq n\leq 40,0\leq a_i\lt p$。

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$