考古学者的安娜和布鲁诺正在伊朗进行遗址调查。他们的角色分配是安娜前往遗址进行挖掘,而布鲁诺则在基地营进行挖掘结果的分析。
挖掘将持续 $Q(=1000)$ 天。每天,安娜使用通信设备将挖掘结果传达给布鲁诺。一天的挖掘结果用一个整数 $X$ 表示。
安娜每天只能使用通信设备一次,设备一次可以发送长度为 $N(=150)$ 的由 $0$ 和 $1$ 组成的数列。
然而,通信设备出现故障,发送的长度 $N$ 的数列中,某些位置无法正常工作,这些位置的值总是被发送为 $0$。安娜在发送前可以确认哪些位置失效,但布鲁诺无法确认。此外,失效的位置及其数量每天可能不同。
为了不延误遗址调查,安娜和布鲁诺请求正在伊朗举办的国际编程比赛的候选人你,编写一个程序来传达挖掘结果。
通信方式
你需要实现两个函数 void Anna(int N,long long X,int K,int P[])
和 long long Bruno(int N,int A[])
来实现以下功能:
Anna
将得到一个长为 $N=150$ 的空白序列和一个不大于 $10^{18}$ 的数字 $X$,这个函数需要为每一位赋予一个 $0$ 或 $1$ 的值来保存 $X$,其中序列中有 $K$ 个位置是损坏的:无论设置为 $0$ 还是 $1$,这些位置的值都恒为 $0$,$P$ 数组保存着这些位置的下标;Bruno
将得到Anna
操作后的序列,这个函数需要依靠这个序列来还原Anna
得到的数字 $X$。
仅支持 C++
语言提交。
你需要实现两个函数。
void Anna( int N, long long X, int K, int P[] )
:这是编码程序,$N$ 代表序列 $S$ 的长度,$X$ 为需要传输的数,$K$ 为损坏位置的数量,$P[]$ 为一个长度为 $K$ 的数组表示损坏的位置编号。
在这个函数中,你可以调用 void Set( int pos, int bit )
,表示把序列 $S$ 的第 $pos$ 位置设置为 $bit$。
long long Bruno( int N, int A[] )
:这是解码程序,其中 $N$ 代表序列长度,而 $A$ 则是 Anna(...)
中调用 Set(...)
的结果。你需要返回解码得到的数。
请注意,这里的数组开头下标皆为 $0$ 。