京都大学プログラミングコンテスト2015

Submission #539078

Source codeソースコード

#include <bits/stdc++.h>
using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

const int K = 60;
const int base = 65;
const int L = 130;

const long NA = 1e18;
long dp[K][2][L];

long solve(long n)
{
    rep(i, K) rep(j, 2) rep(k, L) dp[i][j][k] = NA;
    dp[0][0][base] = 0;
    rep(i, K-1) rep(j, 2) rep(k, 1, L-1) if (dp[i][j][k] != NA) {
        const int ni = i+1;
        const int b = n>>i & 1;
        rep(d, 2) {
            const int s = b+d+j;
            const int nj = s >= 2;
            const int nk = k+d-(s&1);
            dp[ni][nj][nk] = min(dp[ni][nj][nk], dp[i][j][k] | long(d)<<i);
        }
    }
    return dp[K-1][0][base];
}

int main()
{
    int t;
    for (cin >> t; t--; ) {
        long n;
        cin >> n;
        cout << solve(n) << endl;
    }
}

Submission

Task問題 H - Bit Count
User nameユーザ名 stqn
Created time投稿日時
Language言語 C++11 (GCC 4.9.2)
Status状態 AC
Score得点 300
Source lengthソースコード長 977 Byte
File nameファイル名
Exec time実行時間 35 ms
Memory usageメモリ使用量 1048 KB

Test case

Set

Set name Score得点 / Max score Cases
All 300 / 300 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_sample.txt AC 28 ms 924 KB
10_small_00.txt AC 33 ms 928 KB
20_medium_01.txt AC 34 ms 1048 KB
20_medium_02.txt AC 34 ms 1048 KB
20_medium_03.txt AC 34 ms 928 KB
30_large_04.txt AC 34 ms 924 KB
30_large_05.txt AC 35 ms 992 KB
30_large_06.txt AC 34 ms 924 KB
80_power_of_2.txt AC 27 ms 860 KB