Codeforces #112 Div.2 E - Compatible Numbers

問題文 : Compatible Numbers

解法 :
入力される数はすべて22bitで表現されている数だと仮定する. (∵ 4 * 10^6 (=入力の最大値) < 2^22.)

a & b となるbはたくさんあるので, bをaのbitを反転したものとする.

ここで, dp[k] : 数kを, もとの数列の数を変形して作ることが出来るか、とすると
dp[k] = max(dp[kの1のbitを反転したもの]) となるので、これを求める.

dp[aをbit反転したもの]が真であれば、既存の数の中にa & b = 0となるものがあるということがわかる.
配列の参照はO(1)でできるため、クエリ処理にO(N), 前処理にO(2^K * K)かかるため、計算量は, O(2^K * K)である. (ここで、Kはビット数(=22)である.)

コード :

#include <cstdio>
#include <cstring>

using namespace std;

int main()
{
	int n;
	static int ex[1 << 22];
	static int a[1000001];
	
	scanf("%d", &n);
	
	memset(ex, 0, sizeof(ex));
	
	for (int i = 0; i < n; i++){
		scanf("%d", &a[i]);
		ex[a[i]] = a[i];
	}
	
	for (int i = 0; i < 1 << 22; i++){
		for (int j = 0; j < 22; j++){
			if ((i >> j) & 1 && ex[i ^ (1 << j)]){
				ex[i] = ex[i ^ (1 << j)];
			}
		}
	}
	
	for (int i = 0; i < n; i++){
		int inv = ex[((1 << 22) - 1) & ~a[i]];
		printf("%d%c", inv ? inv : -1, i == n - 1 ? '\n' : ' ');
	}
	
	return (0);
}