結果

問題 No.1243 約数加算
ユーザー WarToksWarToks
提出日時 2020-10-02 23:33:56
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,783 bytes
コンパイル時間 3,791 ms
コンパイル使用メモリ 130,388 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-18 00:09:57
合計ジャッジ時間 4,468 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,812 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,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <array>
#include <cassert>
#include <optional>
#include <utility>
#include <vector>
#include <set>
// #include <atcoder/all>

template <class InputIterator>
std::ostream& range_output(std::ostream& os_arg, InputIterator first_arg, InputIterator last_arg){ if(first_arg != last_arg){ do{ os_arg << *(first_arg++); if(first_arg == last_arg) break; os_arg << ' '; } while(true); }  return os_arg; }
template <class Tp> std::ostream& operator << (std::ostream& os_arg, const std::vector<Tp>& arr_arg){ return range_output(os_arg, arr_arg.cbegin(), arr_arg.cend()); }
template <class Tp, std::size_t Size> std::ostream& operator << (std::ostream& os_arg, const std::array<Tp, Size>& arr_arg){ return range_output(os_arg, arr_arg.cbegin(), arr_arg.cend()); }
template <class S, class T> std::ostream& operator << (std::ostream& os_arg, const std::pair<S, T>& pair_arg){ return os_arg << '(' << pair_arg.first << ", " << pair_arg.second << ')'; }

#ifndef ONLINE_JUDGE
    template <typename Head> void dump_out(Head head_arg){ std::cerr << head_arg << '\n'; }
    template <typename Head, typename... Tail>
    void dump_out(Head head_arg, Tail... tail_args){ std::cerr << head_arg << ", "; dump_out(tail_args...); }
    #define dump(...) do { std::cerr << "[in line " << __LINE__ << "] " << #__VA_ARGS__ << " : "; dump_out(__VA_ARGS__); } while(false)
#else
    #define dump(...) (void(0))
#endif

long long int res[200];

int highestbit(long long int x){
    return 63 - __builtin_clzll(x);
}

int len = 0;
void push_integer(const long long int x){ res[len++] = x; }
void out(void){
    std::cout << len << '\n'; assert(len > 0);
    for(int i = 0; ; ){
        std::cout << res[i]; ++i;
        if(i == len){ std::cout << '\n'; break; }
        else std::cout << ' ';
    }
    len = 0;
}

constexpr long long int T = 1'000'000'000'000'000'000;

void solve(void){
    long long int a, b; std::cin >> a >> b; assert(1 <= a and a <= T and 1 <= b and b <= T and a != b);
    while(a > 0 and b > 0){
        const int bit1 = highestbit(a);
        const int bit2 = highestbit(b);
        if(bit1 != bit2) break;
        a ^= (1LL << bit1); b ^= (1LL << bit2);
    }
    const int bit = highestbit(b);
    if(a){
        for(int i = 0; i < bit and a < b; ++i) if((a >> i) & 1){
            a += (1LL << i);
            push_integer(1LL << i);
        }
        b ^= (1LL << bit);
    }
    else push_integer(1LL << bit);
    for(int i = bit - 1; i >= 0; --i) if((b >> i) & 1) push_integer(1LL << i);
    out();
}

int main(void){
    std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); 
    std::cout << std::fixed << std::setprecision(16);
    
    int Q; std::cin >> Q; while(Q--) solve();
    
    return 0;
}
0