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
Submission Time |
|
Task |
H - Bit Count |
User |
MiSawa |
Language |
C++11 (GCC 4.9.2) |
Score |
300 |
Code Size |
1989 Byte |
Status |
AC |
Exec Time |
103 ms |
Memory |
920 KB |
Judge Result
Set Name |
All |
Score / Max Score |
300 / 300 |
Status |
|
Set Name |
Test Cases |
All |
00_sample.txt, 10_small_00.txt, 20_medium_01.txt, 20_medium_02.txt, 20_medium_03.txt, 30_large_04.txt, 30_large_05.txt, 30_large_06.txt, 80_power_of_2.txt |
Case Name |
Status |
Exec Time |
Memory |
00_sample.txt |
AC |
30 ms |
920 KB |
10_small_00.txt |
AC |
103 ms |
796 KB |
20_medium_01.txt |
AC |
94 ms |
800 KB |
20_medium_02.txt |
AC |
98 ms |
920 KB |
20_medium_03.txt |
AC |
95 ms |
804 KB |
30_large_04.txt |
AC |
93 ms |
800 KB |
30_large_05.txt |
AC |
99 ms |
796 KB |
30_large_06.txt |
AC |
97 ms |
920 KB |
80_power_of_2.txt |
AC |
27 ms |
920 KB |