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

Submission #534319

Source codeソースコード

#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

Task問題 H - Bit Count
User nameユーザ名 Mi_Sawa
Created time投稿日時
Language言語 C++11 (GCC 4.9.2)
Status状態 AC
Score得点 300
Source lengthソースコード長 1989 Byte
File nameファイル名
Exec time実行時間 103 ms
Memory usageメモリ使用量 920 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 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