163582025-04-28 18:38:16AblablablaXorcpp17Time limit exceeded 5/100200ms628 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<vector<ll>> dp;
vector<vector<ll>> irany;
ll l, r;

bool igaz(ll akt, ll ind){
    for(ll i = 0; i < ind; i++){
        akt /= 2;
    }

    return akt %= 2;
}

ll megold(ll bit, ll mask){
    if(bit == -1){
        if(igaz(mask, 1) && igaz(mask, 2)){
            return 0;
        } else{
            return -1;
        }
    }

    if(dp[bit][mask] != -2){
        return dp[bit][mask];
    }

    ll vissza = -1;
    ll ind = -1;

    for(ll i = 0; i < 8; i++){
        ll mas = mask;
        vector<bool> ez = {igaz(l, bit), igaz(i, 0), igaz(i, 1), igaz(i, 2), igaz(r, bit)};
        bool jo = 1;

        for(ll j = 0; j < 4; j++){
            if(!igaz(mas, j)){
                if(ez[j] < ez[j + 1]){
                    mas += (1 << j);
                } else if(ez[j] > ez[j + 1]){
                    jo = 0;
                    break;
                }
            }
        }

        if(jo){
            //cout << "ind: " << bit << " " << mask << " \n\tcel: " << bit - 1 << " " << mas << " ::: i: " << i << "\n";
            ll akt = megold(bit - 1, mas);
            if(akt != -1){
                akt = 2*akt + (__builtin_popcount(i) == 1) + (__builtin_popcount(i) == 3);
            }

            if(vissza < akt){
                vissza = akt;
                ind = i;
            }
        }
    }

    irany[bit][mask] = ind;
    return dp[bit][mask] = vissza;
}

int main()
{
    ll t;
    cin >> t;

    while(t--){
        cin >> l >> r;

        ll elso = 63 - __builtin_clzll(r);

        dp.assign(elso + 1, vector<ll>(16, -2));
        irany.assign(elso + 1, vector<ll>(16, -1));

        megold(elso, 0);

        /*for(ll i = 0; i <= elso; i++){
            cout << i << " : ";
            for(ll x : dp[i]){
                cout << x << " ";
            }
            cout << "\n";
        }*/

        ll bit = elso, mask = 0;
        ll x = 0, y = 0, z = 0;

        while(bit >= 0){
            x *= 2;
            x += igaz(irany[bit][mask], 0);
            y *= 2;
            y += igaz(irany[bit][mask], 1);
            z *= 2;
            z += igaz(irany[bit][mask], 2);

            ll mas = mask;
            vector<bool> ez = {igaz(l, bit), igaz(irany[bit][mask], 0), igaz(irany[bit][mask], 1), igaz(irany[bit][mask], 2), igaz(r, bit)};
            bool jo = 1;

            for(ll j = 0; j < 4; j++){
                if(!igaz(mas, j)){
                    if(ez[j] < ez[j + 1]){
                        mas += (1 << j);
                    } else if(ez[j] > ez[j + 1]){
                        jo = 0;
                        break;
                    }
                }
            }

            assert(jo);

            mask = mas;
            bit--;
        }


        cout << x << " " << y << " " << z << "\n";
        assert(l <= x && x < y && y < z && z <= r);
    }
}
SubtaskSumTestVerdictTimeMemory
base5/100
1Accepted0/01ms316 KiB
2Time limit exceeded0/0181ms316 KiB
3Wrong answer0/51ms316 KiB
4Wrong answer0/51ms316 KiB
5Wrong answer0/51ms316 KiB
6Accepted5/51ms336 KiB
7Time limit exceeded0/5200ms420 KiB
8Time limit exceeded0/5200ms316 KiB
9Time limit exceeded0/5199ms432 KiB
10Time limit exceeded0/5184ms316 KiB
11Time limit exceeded0/5184ms508 KiB
12Time limit exceeded0/5200ms424 KiB
13Time limit exceeded0/5200ms432 KiB
14Time limit exceeded0/6184ms316 KiB
15Time limit exceeded0/6200ms316 KiB
16Time limit exceeded0/6180ms628 KiB
17Time limit exceeded0/6181ms316 KiB
18Time limit exceeded0/7187ms316 KiB
19Time limit exceeded0/7184ms316 KiB
20Time limit exceeded0/7200ms316 KiB