CFR 732 F. Anton and School ( Ad hoc, Binary Enumeration )

Problem - F - Codeforces

前言：
Codeforces Round #379 (Div. 2) F. Anton and School - pekempeyのブログ pekempeyさんの記事読んでやっとわかった。

題意：
給相同長度的 B 序列和 C 序列。求是否存在一個 A 序列，滿足

不存在則輸出 -1，否則輸出滿足的任一組 A 序列。

資料規模：
序列長度 1 ≤ N ≤ 2e5
元素大小 0 ≤ B[ i ], C[ i ] ≤ 1e9
時限 2000 ms
記憶體 256 MB

解法：
重點在於發現和利用
x + y = ( x & y ) + ( x | y )
這個性質。
可以推演出
B[ i ] + C[ i ] = N * A[ i ] + SIGMA{ A[ j ] | 0 ≤ j < N }
SIGMA{ B[ i ] + C[ i ] | 0 ≤ i < N } = 2 * N * SIGMA{ A[ j ] | 0 ≤ j < N }
因此可以快速得到所有唯一確定的 A[ i ]。
顯然還要再做個檢查，對每一個 B, C 確定是否依據定義正確。
這部分可以利用預處理，也就是統計位元頻率後，枚舉位元加速。

時間 / 空間複雜度：
O( N lg N )

int N;
vi B;
vi C;

void init(){
    cin >> N;
    B = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> B[ i ];
    C = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> C[ i ];
}

vi A;
vi fbit_A;

void preprocess(){
    ll suma = 0;
    for( int i = 0; i < N; ++i )
        suma += B[ i ] + C[ i ];
    suma /= 2 * N;
    A = vi( N );
    for( int i = 0; i < N; ++i )
        A[ i ] = ( B[ i ] + C[ i ] - suma ) / N;
    fbit_A = vi( 32 ); // frequency of a bit in all As
    for( int i = 0; i < N; ++i )
        for( int j = 0; j < 32; ++j ) if( A[ i ] >> j & 1 )
            ++fbit_A[ j ];
}

void solve(){
    for( int i = 0; i < N; ++i ){
        ll b = 0, c = 0;
        for( int j = 0; j < 32; ++j )
            b += 1LL * fbit_A[ j ] * ( A[ i ] >> j & 1 ) * ( 1 << j ),
            c += 1LL * max( fbit_A[ j ], ( A[ i ] >> j & 1 ) ? N : 0 ) * ( 1 << j );
        if( b != B[ i ] or c != C[ i ] )
            cout << -1 << endl,
            exit( 0 );
    }
    for( int i = 0; i < N; ++i )
        cout << A[ i ] << " \n"[ i + 1 == N ];
}