21 Days Training // Day (8 2/3)~(9 2/3)

G. Binary Cat

Failed problem.

My idea :
We can\’t record the string of every operation, but noticed that we only need to get the char in a specific pos.
Fo, in every operation, check the pos fo char.
If it\’s in L block, jump to L.
Else, jump to R.

Code(Wrong) :

#include <bits/stdc++.h>
using namespace std;
const long long LIM=1000000000000000000;

struct OptBlock {
    long long I1, I2, L;
    /*
    Note :
    I1, I2 : Index of Lstr, Rstr (-1 if id=0 or id=1 )
    L : Length of current str.
    */
};

int main() {
    long long Q;cin >> Q;
    vector<OptBlock> V;
    V.push_back({-1, -1, 1});
    V.push_back({-1, -1, 1});
    for (long long i=0;i<Q;i++) {
        long long Li, Ri, X;cin >> Li >> Ri >> X;
        X--;
        V.push_back({Li, Ri, ((V[Li].L==-1||V[Ri].L==-1)?-1:(V[Li].L+V[Ri].L>LIM?-1:V[Li].L+V[Ri].L))});
        if (Li<=1&&Ri<=1) {
            cout << ((((Li<<1)^Ri)&(1<<(1-X)))>>1);
        }
        else {
            long long block=i+2;
            while (block>1) {
                long long Lix=V[block].I1, Rix=V[block].I2;
                long long LL=V[Lix].L, RL=V[Rix].L;
                if (LL==-1||X<LL) block=Lix, X=X;
                else block=Rix, X-=LL;
            }
            cout << block;
        }
        cout << endl;
    }

    return 0;
}