Codeforces 734F Anton and School

题目描述

Description

Anton goes to school, his favorite lessons are arraystudying. He usually solves all the tasks pretty fast, but this time the teacher gave him a complicated one: given two arrays b and c of length n, find array a, such that:

where a and b means bitwise AND, while a or b means bitwise OR.
Usually Anton is good in arraystudying, but this problem is too hard, so Anton asks you to help.
给你,找到满足符合以下要求的
有解输出,无解输出-1

Input

The first line of the input contains a single integers n (1 ≤ n ≤ 200 000) — the size of arrays b and c.

The second line contains n integers bi (0 ≤ bi ≤ 109) — elements of the array b.

Third line contains n integers ci (0 ≤ ci ≤ 109) — elements of the array c.

Output

If there is no solution, print  - 1.
Otherwise, the only line of the output should contain n non-negative integers ai — elements of the array a. If there are multiple possible solutions, you may print any of them.

input

4
6 8 4 4
16 22 10 10

output

3 5 1 1 

input

5
8 25 14 7 16
19 6 9 4 25

output

-1

题目分析

前置技能
证明如下:
我们按位讨论 每一位可以分为4种情况





于是我们把加和,得到


所以,可以在内拿出,并且有且只有一个解。
但是是与相关联的 我们还要检验是否成立
我们预处理出所有的每一位的个数,对于每个 我们来拆位计算对应的
设现在枚举到第
如果,对的贡献是,对的贡献是
否则,对的贡献是,对的贡献是
所以:


可以在时间内计算出,之后一下就好了

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long read()
{
    long long sum=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') sum=sum*10+(c-'0'),c=getchar();
    return sum;
}
int t,n;
long long a[200005],b[200005],c[200005],sum[200005];
int bits[50];
void work()
{
    scanf("%d",&n);
    memset(sum,0,sizeof sum);
    memset(bits,0,sizeof bits);
    for(int i=1;i<=n;i++) b[i]=read();
    for(int i=1;i<=n;i++) c[i]=read(),sum[i]=b[i]+c[i],sum[0]+=sum[i];
    sum[0]/=2*n;
    for(int i=1;i<=n;i++) a[i]=(sum[i]-sum[0])/n;
    for(int i=1;i<=n;i++)
      for(int j=0;j<31;j++) bits[j]+=( a[i]&(1ll<<j) )?1:0;
    int flag=1;
    for(int i=1;i<=n;i++)
    {
        long long bsum=0,csum=0;
        for(int j=0;j<31;j++)
        { 
            bsum=bsum+(long long)(((a[i]&(1ll<<j))?bits[j]:0)*(1ll<<j));
            csum=csum+(long long)(((a[i]&(1ll<<j))?n:bits[j])*(1ll<<j));
        }
        if(b[i]!=bsum||c[i]!=csum) { flag=0; break; }
    }
    if(flag) for(int i=1;i<=n;i++) printf("%lld%c",a[i],i==n?'\n':' ');
    else printf("-1\n");
}
int main()
{
    scanf("%d",&t);
    while(t--) work();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注