Submission #1556478


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr ll INF = 1e18;

int main() {
    int T;
    cin >> T;
    while(T--) {
        ll N;
        cin >> N;
        vector<vector<vector<ll>>> dp(61, vector<vector<ll>>(120, vector<ll>(2, INF)));
        dp[0][60][0] = 0;
        for(int i = 0; i < 60; ++i) {
            for(int j = 0; j < 120; ++j) {
                for(int k = 0; k < 2; ++k) {
                    if(dp[i][j][k] == INF) {
                        continue;
                    }
                    int d = (N >> i) & 1;
                    for(int l = 0; l < 2; ++l) {
                        int nj = j + ((k + d + l) & 1) - l;
                        int nk = (k + d + l) / 2;
                        dp[i + 1][nj][nk] = min(dp[i + 1][nj][nk], dp[i][j][k] + (ll(l) << i));
                    }
                }
            }
        }
        cout << dp[60][60][0] << endl;
    }
}

Submission Info

Submission Time
Task H - Bit Count
User Suibaka
Language C++14 (GCC 5.4.1)
Score 300
Code Size 965 Byte
Status AC
Exec Time 39 ms
Memory 640 KB

Judge Result

Set Name All
Score / Max Score 300 / 300
Status
AC × 9
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 2 ms 640 KB
10_small_00.txt AC 38 ms 640 KB
20_medium_01.txt AC 35 ms 640 KB
20_medium_02.txt AC 38 ms 640 KB
20_medium_03.txt AC 35 ms 640 KB
30_large_04.txt AC 36 ms 640 KB
30_large_05.txt AC 39 ms 640 KB
30_large_06.txt AC 37 ms 640 KB
80_power_of_2.txt AC 2 ms 640 KB