Submission #534138

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;
typedef long long ll;
static const ll INF = 1000000000000000000ll;
static ll dp[61][61][61][2];

int main(){
	ios_base::sync_with_stdio(false);
	int T;
	cin >> T;
	while(T--){
		ll x;
		cin >> x;
		memset(dp, 0, sizeof(dp));
		for(int i = 0; i <= 60; ++i){
			for(int j = 0; j <= 60; ++j){
				for(int k = 0; k <= 60; ++k){
					dp[i][j][k][0] = dp[i][j][k][1] = INF;
				}
			}
		}
		dp[0][0][0][0] = 0;
		for(int i = 0; i < 60; ++i){
			for(int j = 0; j <= i; ++j){
				for(int k = 0; k <= i; ++k){
					const int d = (x >> i) & 1;
					// carry = 0, add 0
					dp[i + 1][j][k + d][0] =
						min(dp[i + 1][j][k + d][0], dp[i][j][k][0]);
					// carry = 0, add 1
					dp[i + 1][j + 1][k + (d ^ 1)][d] =
						min(dp[i + 1][j + 1][k + (d ^ 1)][d], dp[i][j][k][0] + (1ll << i));
					// carry = 1, add 0
					dp[i + 1][j][k + (d ^ 1)][d] =
						min(dp[i + 1][j][k + (d ^ 1)][d], dp[i][j][k][1]);
					// carry = 1, add 1
					dp[i + 1][j + 1][k + d][1] =
						min(dp[i + 1][j + 1][k + d][1], dp[i][j][k][1] + (1ll << i));
				}
			}
		}
		ll answer = INF;
		for(int i = 0; i <= 60; ++i){
			answer = min(answer, dp[60][i][i][0]);
		}
		cout << answer << endl;
	}
	return 0;
}

Submission Info

Judge Result