#378214 (C++11) No.3 ビットすごろく

提出ソース

結果

問題	No.3 ビットすごろく
ユーザー	佐藤淳平
提出日時	2019-09-11 23:07:27
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	2 ms / 5,000 ms
コード長	7,367 bytes
コンパイル時間	1,474 ms
コンパイル使用メモリ	164,820 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-07-01 09:30:14
合計ジャッジ時間	2,345 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,812 KB
testcase_01	AC	1 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	1 ms 6,940 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	1 ms 6,940 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	2 ms 6,940 KB
testcase_14	AC	2 ms 6,940 KB
testcase_15	AC	2 ms 6,944 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	1 ms 6,940 KB
testcase_19	AC	2 ms 6,944 KB
testcase_20	AC	2 ms 6,944 KB
testcase_21	AC	2 ms 6,944 KB
testcase_22	AC	2 ms 6,940 KB
testcase_23	AC	2 ms 6,940 KB
testcase_24	AC	2 ms 6,944 KB
testcase_25	AC	2 ms 6,944 KB
testcase_26	AC	2 ms 6,944 KB
testcase_27	AC	2 ms 6,944 KB
testcase_28	AC	2 ms 6,940 KB
testcase_29	AC	2 ms 6,944 KB
testcase_30	AC	1 ms 6,940 KB
testcase_31	AC	1 ms 6,944 KB
testcase_32	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

using i8   = int8_t; using i16  = int16_t; using i32  = int32_t; using i64  = int64_t;
using u8   = uint8_t; using u16  = uint16_t; using u32  = uint32_t; using u64  = uint64_t;
using f32  = float; using f64  = double;
using vi32  = std::vector<i32>;   using vu32  = std::vector<u32>;   using vf32  = std::vector<f32>;
using vi64  = std::vector<i64>;   using vu64  = std::vector<u64>;   using vf64  = std::vector<f64>;
using vvi32 = std::vector<vi32>;  using vvu32 = std::vector<vu32>;  using vvf32 = std::vector<vf32>;
using vvi64 = std::vector<vi64>;  using vvu64 = std::vector<vu64>;  using vvf64 = std::vector<vf64>;
using pi32  = std::pair<i32,i32>; using pu32  = std::pair<u32,u32>; using pf32  = std::pair<f32,f32>;
using pi64  = std::pair<i64,i64>; using pu64  = std::pair<u64,u64>; using pf64  = std::pair<f64,f64>;

#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) ((obj).rbegin(),(obj).rend())
#define SZ(obj) ((i32)(obj).size())
#define EACH(it,o) for(auto it=(o).begin();it!=(o).end();++it)
#define IN(l,n,r) ((l)<=(n) && (n)<(r))
#define UNIQUE(obj) (obj).erase(std::unique(ALL(obj)),(obj).end())
#define CLR(ar,val) memset(ar, val, sizeof(ar))
#define FOR(i,a,b) for(i32 i=(i32)(a); i<(i32)(b); i++)
#define RFOR(i,a,b) for(i32 i=(i32)(b)-1;i>=(i32)(a);--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define PRINT(n) cout << (n) <<"\n";
#define cauto const auto&
#define mp make_pair
#define pb push_back

const i32 INF   = 0x3F3F3F3F;
const i64 INF64 = 0x3F3F3F3F3F3F3F3F;
const f64 EPS   = 1e-8;
const i32 MOD   = 1000000007;
static const f64 PI     = 3.1415926535897932;
static const f64 NAPIER = 2.7182818284590452;
const char alphabetl[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
const char alphabetu[26] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
i32 dx[4] = {1, 0, -1, 0};
i32 dy[4] = {0, 1, 0, -1};

template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

i64 BIT_COUNT_ONES(i64 x) {
    return __builtin_popcountll(x);
}
i64 BIT_COUNT_ZEROS(i64 x) {
    return 64 - BIT_COUNT_ONES(x);
}

//input pair tuple vector
template<typename T1,typename T2> std::istream& operator >> (std::istream& is,std::pair<T1,T2>& p){is>>p.first>>p.second;return is;}
template<typename T1> std::istream& operator >> (std::istream& is,std::tuple<T1>& t){is >> std::get<0>(t);return is;}
template<typename T1,typename T2> std::istream& operator >> (std::istream& is,std::tuple<T1,T2>& t){is >> std::get<0>(t) >> std::get<1>(t);return is;}
template<typename T1,typename T2,typename T3> std::istream& operator >> (std::istream& is,std::tuple<T1,T2,T3>& t){is >>std::get<0>(t)>>std::get<1>(t)>>std::get<2>(t);return is;}
template<typename T1,typename T2,typename T3,typename T4> std::istream& operator >> (std::istream& is,std::tuple<T1,T2,T3,T4>& t){is >> std::get<0>(t)>>std::get<1>(t)>>std::get<2>(t)>>std::get<3>(t);return is;}
template<typename T1,typename T2,typename T3,typename T4,typename T5> std::istream& operator >> (std::istream& is, const std::tuple<T1,T2,T3,T4,T5>& t){is >> std::get<0>(t) >> std::get<1>(t) >> std::get<2>(t) >> std::get<3>(t) >> std::get<4>(t);return is;}
template<typename T1,typename T2,typename T3,typename T4,typename T5,typename T6> std::istream& operator >> (std::istream& is, const std::tuple<T1,T2,T3,T4,T5,T6>& t){is >> std::get<0>(t) >> std::get<1>(t) >> std::get<2>(t) >> std::get<3>(t) >> std::get<4>(t) >> std::get<5>(t);return is;}
template<typename T1,typename T2,typename T3,typename T4,typename T5,typename T6,typename T7> std::istream& operator >> (std::istream& is, const std::tuple<T1,T2,T3,T4,T5,T6,T7>& t){is >> std::get<0>(t) >> std::get<1>(t) >> std::get<2>(t) >> std::get<3>(t) >> std::get<4>(t) >> std::get<5>(t) >> std::get<6>(t);return is;}
template<typename T> std::istream& operator >> (std::istream& is,std::vector<T>& as){REP(i,SZ(as))is >>as[i];return is;}

//output set pair map tuple vector
template<typename T> std::ostream& operator << (std::ostream& os, const std::set<T>& ss){for(auto a:ss){if(a!=ss.begin())os<<" "; os<<a;}return os;}
template<typename T1,typename T2> std::ostream& operator << (std::ostream& os, const std::pair<T1,T2>& p){os<<p.first<<" "<<p.second;return os;}
template<typename K,typename V> std::ostream& operator << (std::ostream& os, const std::map<K,V>& m){bool isF=true;for(auto& p:m){if(!isF)os<<std::endl;os<<p;isF=false;}return os;}
template<typename T1> std::ostream& operator << (std::ostream& os, const std::tuple<T1>& t){os << std::get<0>(t);return os;}
template<typename T1,typename T2> std::ostream& operator << (std::ostream& os, const std::tuple<T1,T2>& t){os << std::get<0>(t)<<" "<<std::get<1>(t);return os;}
template<typename T1,typename T2,typename T3> std::ostream& operator << (std::ostream& os, const std::tuple<T1,T2,T3>& t){os << std::get<0>(t)<<" "<<std::get<1>(t)<<" "<<std::get<2>(t);return os;}
template<typename T1,typename T2,typename T3,typename T4> std::ostream& operator << (std::ostream& os, const std::tuple<T1,T2,T3,T4>& t){os << std::get<0>(t)<<" "<<std::get<1>(t)<<" "<<std::get<2>(t)<<" "<<std::get<3>(t);return os;}
template<typename T1,typename T2,typename T3,typename T4,typename T5> std::ostream& operator << (std::ostream& os, const std::tuple<T1,T2,T3,T4,T5>& t){os << std::get<0>(t)<<" "<<std::get<1>(t)<<" "<<std::get<2>(t)<<" "<<std::get<3>(t)<<" "<<std::get<4>(t);return os;}
template<typename T1,typename T2,typename T3,typename T4,typename T5,typename T6> std::ostream& operator << (std::ostream& os, const std::tuple<T1,T2,T3,T4,T5,T6>& t){os << std::get<0>(t)<<" "<<std::get<1>(t)<<" "<<std::get<2>(t)<<" "<<std::get<3>(t)<<" "<<std::get<4>(t)<<" "<<std::get<5>(t);return os;}
template<typename T1,typename T2,typename T3,typename T4,typename T5,typename T6,typename T7> std::ostream& operator << (std::ostream& os, const std::tuple<T1,T2,T3,T4,T5,T6,T7>& t){os << std::get<0>(t)<<" "<<std::get<1>(t)<<" "<<std::get<2>(t)<<" "<<std::get<3>(t)<<" "<<std::get<4>(t)<<" "<<std::get<5>(t)<<" "<<std::get<6>(t);return os;}
template<typename T> std::ostream& operator << (std::ostream& os, const std::vector<T>& as){REP(i,as.size()){if(i!=0)os<<" "; os<<as[i];}return os;}
template<typename T> std::ostream& operator << (std::ostream& os, const std::vector<std::vector<T>>& as){REP(i,SZ(as)){if(i!=0)os<<std::endl; os<<as[i];}return os;}

void Main();
int main() {std::cin.tie(nullptr);std::ios::sync_with_stdio(false);std::cout<<std::fixed<<std::setprecision(15);Main();return 0;}


void Main() {
    i64 N; cin >> N;

    vi64 dp(N+1, -1);
    dp[1] = 1;
    queue<i64> q;
    q.push(1);
    while(!q.empty()) {
        i64 n = q.front(); q.pop();
        if(n == N) break;
        i64 nn = n + BIT_COUNT_ONES(n);
        if (0 < nn && nn <= N && dp[nn] == -1) {
            q.push(nn);
            dp[nn] = dp[n] + 1;
        }
        i64 nb = n - BIT_COUNT_ONES(n);
        if (0 < nb && nb <= N && dp[nb] == -1) {
            q.push(nb);
            dp[nb] = dp[n] + 1;
        }
    }
    cout << dp[N] << endl;
}

yukicoder

結果

テストケース

ソースコード