UTPC2011 I: ビット演算

問題概要

数列x[i]とy[i]が与えられる(長さ8以下, 0

解法

公式の解説を参考にして解いた。文字列を前に追加するのには長さに比例したコストが必要なことを留意しないとTLEの可能性があるかもしれない。

#include <cstdio>
#include <vector>
#include <string>
using namespace std;

int N;
int xs[10], ys[10];
string bins[] = {"1", "2", "4", "8", "16", "32", "64", "128", "256"};
vector<int> lower_bit[10];

string subsolve(int b, int x){
	string ret = bins[b];
	int cnt = 0;
	for(int i=0; i<=b; i++){
		bool on = ((x>>i)&1);
		ret += "&(" + (on?string("x"):string("(~x)")) + "*" + bins[b-i] + "))";
		cnt++;
	}
	return string(cnt,'(') + ret;
}

string solve(){
	string ret = "0";
	int cnt = 0;
	for(int i=0; i<8; i++){
		for(int j=0; j<N; j++)if((ys[j]>>i)&1){
			lower_bit[i].push_back( xs[j]&((1<<(i+1))-1) );
		}
	}
	for(int i=0; i<8; i++){
		for(int j=0; j<(int)lower_bit[i].size(); j++){
			ret += "|" + subsolve(i,lower_bit[i][j]) + ")";
			cnt++;
		}
	}
	return string(cnt,'(') + ret;
}

int main(){
	scanf("%d",&N);
	for(int i=0; i<N; i++){
		scanf("%d%d",xs+i,ys+i);
	}
	puts(solve().c_str());
	return 0;
}