Submission #535241


Source Code Expand

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;

int T;
typedef long long LL;
LL ans, n, dp[70][70][70];
int f[70];
int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%lld", &n);
        memset(f, 0, sizeof(f));
        int cnt = 0;
        for(int i=0; i<64; i++){
            if(n%2==1){
                f[i] = 1;
                cnt++;
            }
            n/=2;
        }
        memset(dp, -1, sizeof(dp));
        for(int i=0; i<64; i++){
            if(f[i]){
                dp[i][cnt][0] = 0;
                break;
            }
        }
        ans = -1;
        LL cur = 1;
        for(int i=0; i<60; i++, cur*=2){
            for(int j=0; j<=cnt; j++){
                for(int k=0; k<=cnt; k++){
                    if(dp[i][j][k] == -1)   continue;
                    if(j == k){
                        if(ans == -1 || dp[i][j][k]<ans){
                            ans = dp[i][j][k];
                            continue;
                        }
                    }
                        for(int l=i+1; l<60; l++){
                            if(f[l]){
                                if(dp[l][j][k]==-1 || dp[i][j][k]<dp[l][j][k]){
                                    dp[l][j][k] = dp[i][j][k];
                                    break;
                                }
                            }
                        }
                        for(int l=i+1; l<60; l++){
                            if(!f[l]){
                                int x = l - i;
                                if(j>=x){
                                    if(dp[l][j-x+1][k+1]==-1 || dp[i][j][k]+cur<dp[l][j-x+1][k+1]){
                                        dp[l][j-x+1][k+1] = dp[i][j][k] + cur;
                                    }
                                }
                                break;
                            }
                        }
                }
            }
        }
        for(int i=0; i<60; i++){
            for(int j=0; j<60; j++){
                if(dp[i][j][j] != -1){
                    if(ans==-1 || dp[i][j][j]<ans)    ans = dp[i][j][j];
                }
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

Submission Info

Submission Time
Task H - Bit Count
User hongrock
Language C++ (GCC 4.9.2)
Score 300
Code Size 2335 Byte
Status AC
Exec Time 148 ms
Memory 3480 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:12:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &T);
                    ^
./Main.cpp:14:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &n);
                          ^

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 32 ms 3356 KB
10_small_00.txt AC 109 ms 3480 KB
20_medium_01.txt AC 112 ms 3360 KB
20_medium_02.txt AC 120 ms 3356 KB
20_medium_03.txt AC 114 ms 3312 KB
30_large_04.txt AC 141 ms 3364 KB
30_large_05.txt AC 148 ms 3360 KB
30_large_06.txt AC 140 ms 3476 KB
80_power_of_2.txt AC 32 ms 3360 KB