Codeforces 1463B Find The Array

题意

给一个长度为$n$的数组$a$，令$S$为其总和，定义数组$b$为美丽的当且仅当：

$1\leq b_i\leq 10^9(1\leq i\leq n)$
对于$(b_i,b_{i+1})$，$b_i$整除$b_{i+1}$或者$b_{i+1}$整除$b_i$
$2\sum_{i=1}^{n}|a_i-b_i|\leq S$

输出$b$数组。

分析

首先难办的是第三个条件，我们想一想，如果这个条件要满足，尽量$b_i\in[a_i*1.5,a_i*0.5]$，那么我们看下界可以注意到，如果一个数是$2$的幂，那么其二分之一即是下界，而若其不是$2$的幂，那么若其只保留二进制最高位，那么其必然在区间里。

对于第二个条件也有直觉都是同一因子的倍数，而对于第三个条件的$2$，也可以想到构造$2$的幂数组。

#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define repd(z, x, y) for(int z=x;z>=y;--z)
#define com bool operator<(const node &b)const
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int maxn = (ll) 1e6 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
int T = 1;

void solve() {
    vector<int> v;
    rep(i, 0, 35)v.push_back(1ll << i);
    int n;
    cin >> n;
    rep(i, 1, n) {
        int x;
        cin >> x;
        if (x == 1)
            cout << 1 << ' ';
        else {
            int pos = lower_bound(v.begin(), v.end(), x) - v.begin() - 1;
            cout << v[pos] << ' ';
        }
    }
    cout << '\n';
}

signed main() {
    start;
    cin >> T;
    while (T--)
        solve();
    return 0;
}