Problem Statement
You are given an array of $n$ non-negative integers.
You want to answer given $q$ independent scenarios. In the $i$-th scenario, you are allowed to perform the following operation at most $b_i$ times:
- Choose an element of the array and increase it by $1$.
Your goal is to maximize the number of bits that are equal to $1$ in the bitwise OR of all numbers in the array. Find this number for each scenario.
Editorial
Notice that the answer is at most $31$ and the number of operation required for each answer is monotonic, so we only need to compute the minimal operation time for each answer.
Notice that we will only choose some bits which are initially $0$, and change them to $1$. It is easy to prove.
Here we define TRIGGER operation for further explanation:
To switch the $i$-th bit, the best option is to find the element $a_j$ such that $a_j \bmod 2^i$ is the largest one, so we merely need $2^i - \left(a_j \bmod 2^i\right)$ operations.
However, here is a problem that after this operation, $a_j \bmod 2^{i - 1}$ will become $0$. Hence, the bitwise OR in lower bits might change.
Upon closer examination, we will discover this is not a big deal. We can simply repeat the TRIGGER operation to make the lower bits all be $1$. It is optimal, because even if we choose $a_k$ instead of $a_j$ to increase, it is equivalent to increasing $a_j$ to $2^i$, and then, increasing $a_k$ to $a_j$.
The needed computational amount is $31^2 \cdot n$.
Code
struct SNOWFLAKE {
static constexpr char FIO_[] = "";
static constexpr char FIN_[] = "";
static constexpr char FOUT_[] = "";
static constexpr bool MTS = true;
static constexpr bool SPC_MTS = false;
template <typename Ty>
using vla = std::vector<Ty>;
template <typename Ty1, typename Ty2>
using pair = std::pair<Ty1, Ty2>;
using string = std::string;
using ll = long long int;
using ull = unsigned long long int;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vb = vla<bool>;
using vi = vla<int>;
using vl = vla<ll>;
static constexpr int INF32 = 0x3ffffffe;
static constexpr ll INF64 = 0x3ffffffffffffffe;
template <typename Ty1, typename Ty2>
static void ckmin(Ty1& x, Ty2 y) { if (y < x) x = y; }
template <typename Ty1, typename Ty2>
static void ckmax(Ty1& x, Ty2 y) { if (x < y) x = y; }
template <typename Ty = int>
static vla<Ty> bva(int n) {
vla<Ty> a(n);
for (auto& i : a) std::cin >> i;
return a;
}
SNOWFLAKE() {
if (strlen(FIO_) != 0) {
freopen((std::string(FIO_) + ".in").c_str(), "r", stdin);
freopen((std::string(FIO_) + ".out").c_str(), "w", stdout);
} else {
if (strlen(FIN_) != 0) freopen(FIN_, "r", stdin);
if (strlen(FOUT_) != 0) freopen(FOUT_, "w", stdout);
}
std::cin.tie(nullptr)->sync_with_stdio(false);
}
~SNOWFLAKE() {
int t = 1;
if (MTS && !SPC_MTS) std::cin >> t;
for (int i = 0; i < t || SPC_MTS; ++i) {
if (main(i) != 0) return;
}
}
int bor(vi a) {
int ret = 0;
for (auto i : a) ret |= i;
return ret;
}
int main([[maybe_unused]] int TNO) {
int n, q; std::cin >> n >> q;
vi a = bva(n);
int s = __builtin_popcount(bor(a));
vi tar(32, 0);
for (int i = s + 1; i < 32; ++i) {
int p = 0;
while ((bor(a) >> p & 1) != 0) ++p;
tar[i] = tar[i - 1];
for (int j = p; j >= 0; --j) {
if ((bor(a) >> j & 1) != 0) continue;
int l = 0;
for (int k = 1; k < n; ++k) {
if ((a[k] & ((1 << j) - 1)) > (a[l] & ((1 << j) - 1))) l = k;
}
tar[i] += (1 << j) - (a[l] & ((1 << j) - 1));
a[l] += (1 << j) - (a[l] & ((1 << j) - 1));
}
}
while (q--) {
int m; std::cin >> m;
std::cout << upper_bound(tar.begin(), tar.end(), m) - tar.begin() - 1 << "\n";
}
return 0;
}
} SNOWFLAKE;