牛牛的or

NC21300. 牛牛的or

描述

给你两个长度为n的数组a,b
是否能构造出长度为n+1的x数组使得
for each i between 0 and n-1
x[i] or x[i+1] = a[i]
x[i] + x[i+1] = b[i]

输入描述

第一行输入一个整数n (1 ≤ n ≤ 50)
第二行输入n个整数a_i
第三行输入n个整数b_i
0 ≤ a_i,b_i ≤ 10¹⁸

输出描述

输出"Possible"如果能构造出来
否则输出"Impossible"

示例1

输入:

1
7
11

输出:

Possible

示例2

输入:

1
11
7

输出:

Impossible

示例3

输入:

5
3 3 7 5 7
3 5 7 9 11

输出:

Possible

示例4

输入:

3
1 100 1000
100 1000 10000

输出:

Impossible

示例5

输入:

3
261208776456074191 261208776456074191 261208776456074191
333333333333333333 333333333333333333 333333333333333333

输出:

Possible

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 9ms, 内存消耗: 668K, 提交时间: 2021-09-26 21:03:33

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100;
int n,b[N],c[N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++) scanf("%d",&c[i]),c[i]-=b[i];
	ll ans=1;
	for(int i=0;i<N;i++){
		int a0=1,a1=1;
		for(int j=1;j<=n;j++){
			int eb=b[j]>>i&1;
			int ec=c[j]>>i&1;
			int b0=0,b1=0;
			if(eb&&ec) b1=a1;
			if(eb&&!ec) {
				b1=a0;
				b0=a1;
			}
			if(!eb&&!ec) b0=a0;
			a0=b0,a1=b1;
		}
		ans*=(a0+a1);
	}
	if(ans==0) puts("Impossible");
	else puts("Possible") ;
	return 0;
}