Code
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, q;
cin >> n >> q;
vector<long long> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<long long> global_copy_of_a = a;
for (int zz = 0; zz < q; zz++) {
a = global_copy_of_a;
long long k;
cin >> k;
// Iterate through higher order bits to lower order.
long long answer = 0;
// What's the safest highest bit?
for (int bit = 62; bit >= 0; bit--) {
int current_and = 1;
for (int i = 0; i < n; i++) {
if ((1LL << bit) & a[i]) {
current_and &= 1;
} else {
current_and &= 0;
}
}
if (current_and == 1) {
answer |= (1LL << bit);
continue;
}
// Else, try to use it.
long long need = 0;
// Don't accumulate sum all at once to prevent overflow.
bool effort_success = true;
long long previous_k = k;
auto local_copy_of_a = a;
for (int i = 0; i < n; i++) {
if ((1LL << bit) & a[i]) {
// If the bit is already set, skip it.
} else {
long long copy = a[i];
long long cost;
// Borrow it if possible.
if (bit >= 1 && ((1LL << (bit - 1) & a[i]) != 0)) {
cost = 1LL << (bit - 1);
// Unset the lower order bit.
a[i] &= ~(1LL << (bit - 1));
} else {
cost = 1LL << bit;
}
if (k >= cost) {
k -= cost;
} else {
effort_success = false;
break;
}
}
}
if (!effort_success) {
a = local_copy_of_a;
// Reverse all operations
k = previous_k;
} else {
answer |= (1LL << bit);
}
}
cout << answer << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, q;
cin >> n >> q;
vector<long long> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<long long> global_copy_of_a = a;
for (int zz = 0; zz < q; zz++) {
a = global_copy_of_a;
long long k;
cin >> k;
// Iterate through higher order bits to lower order.
long long answer = 0;
// What's the safest highest bit?
for (int bit = 62; bit >= 0; bit--) {
int current_and = 1;
for (int i = 0; i < n; i++) {
current_and &= ((1LL << bit) & a[i]) != 0;
}
if (current_and == 1) {
// Clear all higher bits.
for (int i = 0; i < n; i++) {
a[i] &= ~(1LL << bit);
}
answer |= (1LL << bit);
continue;
}
// Don't accumulate sum all at once to prevent overflow.
bool effort_success = true;
long long previous_k = k;
auto local_copy_of_a = a;
for (int i = 0; i < n; i++) {
if ((1LL << bit) & a[i]) {
// If the bit is already set, skip it.
} else {
// You can assume that higher order bits don't exist.
long long cost = (1LL << bit) - a[i];
if (k >= cost) {
k -= cost;
} else {
effort_success = false;
break;
}
// If it is possible to turn on this bit, it means that
// the new number is 000 (1) 0000.
a[i] = (1LL << bit);
}
}
if (!effort_success) {
// Reverse all operations
a = local_copy_of_a;
k = previous_k;
} else {
answer |= (1LL << bit);
}
// Clear all higher bits.
for (int i = 0; i < n; i++) {
a[i] &= ~(1LL << bit);
}
}
cout << answer << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, q;
cin >> n >> q;
vector<long long> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<long long> global_copy_of_a = a;
for (int zz = 0; zz < q; zz++) {
a = global_copy_of_a;
long long k;
cin >> k;
// Iterate through higher order bits to lower order.
long long answer = 0;
// What's the safest highest bit?
for (int bit = 62; bit >= 0; bit--) {
int current_and = 1;
for (int i = 0; i < n; i++) {
if ((1LL << bit) & a[i]) {
current_and &= 1;
} else {
current_and &= 0;
}
}
if (current_and == 1) {
answer |= (1LL << bit);
continue;
}
// Else, try to use it.
long long need = 0;
// Don't accumulate sum all at once to prevent overflow.
bool effort_success = true;
long long previous_k = k;
auto local_copy_of_a = a;
for (int i = 0; i < n; i++) {
if ((1LL << bit) & a[i]) {
// If the bit is already set, skip it.
} else {
// If it is possible to turn on this bit, it means that
// the new number is xyz (1) 0000. Hence, turn of all lower
// order bits.
long long relief = 0;
for (int lower = bit - 1; lower >= 0; lower--) {
if ((1LL << lower) & a[i]) {
// Unset the lower order bit.
a[i] &= ~(1LL << (lower));
relief += (1LL << lower);
}
}
long long cost = (1LL << bit) - relief;
if (k >= cost) {
k -= cost;
} else {
effort_success = false;
break;
}
}
}
if (!effort_success) {
a = local_copy_of_a;
// Reverse all operations
k = previous_k;
} else {
answer |= (1LL << bit);
}
}
cout << answer << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, q;
cin >> n >> q;
vector<long long> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<long long> global_copy_of_a = a;
for (int zz = 0; zz < q; zz++) {
a = global_copy_of_a;
long long k;
cin >> k;
// Iterate through higher order bits to lower order.
long long answer = 0;
// What's the safest highest bit?
for (int bit = 62; bit >= 0; bit--) {
int current_and = 1;
for (int i = 0; i < n; i++) {
current_and &= ((1LL << bit) & a[i]) != 0;
}
if (current_and == 1) {
answer |= (1LL << bit);
continue;
}
// Don't accumulate sum all at once to prevent overflow.
bool effort_success = true;
long long previous_k = k;
auto local_copy_of_a = a;
for (int i = 0; i < n; i++) {
if ((1LL << bit) & a[i]) {
// If the bit is already set, skip it.
} else {
// (a[i] % 2^bit) is a fancy way to clear higher order
// bits
long long cost = (1LL << bit) - (a[i] % (1LL << bit));
if (k >= cost) {
k -= cost;
} else {
effort_success = false;
break;
}
// If it is possible to turn on this bit, it means that
// the new number is 000 (1) 0000.
// Not really, because we there could be some set bits in
// higher order bits. But then again, we don't care, we
// are not gonna use them anyway, since we are using a
// trick to clear higher order bits.
a[i] = (1LL << bit);
}
}
if (!effort_success) {
// Reverse all operations
a = local_copy_of_a;
k = previous_k;
} else {
answer |= (1LL << bit);
}
}
cout << answer << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}