Submission #534319

---

Source Code Expand

#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
#define rall(x) (x).rbegin(),(x).rend()
#define REP(i,b,n) for(int i=(int)(b);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define repsz(i,v) rep(i,(v).size())
#define aur auto&
#define bit(n) (1LL<<(n))
#define eb emplace_back
#define mt make_tuple
#define fst first
#define snd second
using namespace std;
typedef long long ll;
//#define int long long
template<class C>int size(const C &c){ return c.size(); }
template<class T,class U>bool chmin(T&a,const U&b){if(a<=b)return false;a=b;return true;}
template<class T,class U>bool chmax(T&a,const U&b){if(a>=b)return false;a=b;return true;}

constexpr size_t B = 65;
constexpr size_t geta = 65;
bool solve(){
    long long n; cin >> n;
    constexpr long long inf = numeric_limits<long long>::max() / 10;
    auto dp = vector<vector<ll>>(B*2+5, vector<ll>(2, inf));
    // dp[bitcount(X) - bitcount(X+N) + geta][carry] = min X
    dp[geta][0] = 0;
    rep(b, 60){
        auto qb = vector<vector<ll>>(B*2+5, vector<ll>(2, inf));
        rep(i, 2*B+5) if(1 < i and i < B*2+3) rep(k, 2){
            // この bit を 0 にする
            if(k && (n>>b&1)) chmin(qb[i][1], dp[i][k]);
            else if(k | (n>>b&1)) chmin(qb[i-1][0], dp[i][k]);
            else chmin(qb[i][0], dp[i][k]);
            // この bit を 1 にする
            if(k && (n>>b&1)) chmin(qb[i][1], dp[i][k] + (1LL<<b));
            else if(k | (n>>b&1)) chmin(qb[i+1][1], dp[i][k] + (1LL<<b));
            else chmin(qb[i][0], dp[i][k] + (1LL<<b));
        }
        swap(dp, qb);
    }
    long long res = dp[geta][0];
    cout << res << endl;
    return true;
}
signed main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << std::fixed << std::setprecision(10);
    int t; cin >> t;
    rep(_, t) solve();
    return 0;
}
// vim:set foldmethod=marker commentstring=//%s:

Submission Info

Judge Result