2309:BST

keyword

2分木　C++

概要

上のような2分木がある。x(<2^31)が与えられたときxの子孫のなかで最小のものと最大のものを答える問題。
2進数に書き直すとルールが見えてくる。実装は簡単。

ll toLeft(ll x){
    if(x&1) return x;
    int i;
    REPONE(i,40)if(x&(1<<i))break;
    return toLeft(x - (1<<(i-1)));
}

ll toRight(ll x){
    if(x&1) return x;
    int i;
    REPONE(i,40)if(x&(1<<i))break;
    return toRight(x + (1<<(i-1)));
}

int main(){
    int n;
    ll x;
    scanf("%d",&n);

    while(n--){
        scanf("%lld",&x);
        printf("%lld %lld\n", toLeft(x), toRight(x));
    }

    return 0;
}