In this HackerEarth Maximizing expressions problem solution You are given three arrays A, B, and C. All the three arrays consist of N integers.
You must perform the following operation on each index exactly one time:
Convert(i): Select a positive value D such that Ci & D = D, and update Bi = Bi xor D.
Here, xor and & denotes the bitwise XOR operation and bitwise AND operation.
You are required to maximize the following expression:
S = sigma(n, i = 1) Ai xor Bi
HackerEarth Maximizing expressions problem solution.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100009;
ll n, m, x, y, z;
ll ara1[maxn], ara2[maxn], ara3[maxn];
bool getBit(ll val, ll pos)
{
return (bool)(val & (1LL << pos));
}
int main()
{
cin >> n;
for(ll i = 1; i <= n; i++) scanf("%lld", &ara1[i]);
for(ll i = 1; i <= n; i++) scanf("%lld", &ara2[i]);
for(ll i = 1; i <= n; i++) scanf("%lld", &ara3[i]);
ll anss = 0;
for(ll i = 1; i <= n; i++){
ll tmp = 0;
bool flg = false;
for(ll j = 0; j < 30; j++){
ll mx1 = getBit(ara1[i], j) ^ getBit(ara2[i], j);
ll mx2 = getBit(ara1[i], j) ^ getBit(ara2[i], j) ^ getBit(ara3[i], j);
tmp += (1LL << j) * max(mx1, mx2);
if(mx2 && getBit(ara3[i], j)) flg = true;
}
if(!flg){
ll lstSetbit = 0;
while(getBit(ara3[i], lstSetbit) == 0) lstSetbit++;
if(getBit(tmp, lstSetbit) == 0) assert(false);
tmp -= (1LL << lstSetbit);
}
anss += tmp;
}
cout << anss << endl;
return 0;
}
0 Comments