Cod sursa(job #3338240)

Utilizator Andrei-Dani-10Pisla Andrei Daniel Andrei-Dani-10 Data 1 februarie 2026 19:35:01
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <fstream>

#include <utility>
#define x first
#define y second

using namespace std;

ifstream in("xormax.in");
ofstream out("xormax.out");

typedef pair <int, int> pii;
const int nmax = 1e5, lgmax = 31, maxint = (1 << 30);
int n, a[nmax + 2], xormaxx; pii bestt;

struct prefixnode{
    int lastt;
    prefixnode *nextt[2];

    prefixnode() : lastt(0){
        nextt[0] = NULL;
        nextt[1] = NULL;
    }
};

struct prefixtree{
    prefixnode *root;

    void updateadd(int xx, int where){
        prefixnode *node = root;

        for(int b = lgmax; b >= 0; b--){
            int bit = !!(xx & (1 << b));

            if((node -> nextt[bit]) == NULL)
                node -> nextt[bit] = new prefixnode();

            node = (node -> nextt[bit]);
            (node -> lastt) = where;
        }

        return;
    }

    pii queryxormax(int xx){
        prefixnode *node = root; pii qry = make_pair(0, maxint);

        for(int b = lgmax; b >= 0; b--){
            int bit = !!(xx & (1 << b));

            if((node -> nextt[bit ^ 1]) != NULL){
                node = (node -> nextt[bit ^ 1]);
                qry.x |= (1 << b); qry.y = min(qry.y, (node -> lastt));
            }else if((node -> nextt[bit]) != NULL){
                node = (node -> nextt[bit]);
                qry.y = min(qry.y, (node -> lastt));
            }
        }

        return qry;
    }
} mytrie;

int main(){

    in>>n; mytrie.root = new prefixnode();
    for(int i = 1; i <= n; i++){
        in>>a[i], a[i] ^= a[i - 1];
    }

    mytrie.updateadd(0, 0);
    for(int i = 1; i <= n; i++){

        pii qry = mytrie.queryxormax(a[i]);
        mytrie.updateadd(a[i], i);

        if(xormaxx < qry.x){
            xormaxx = qry.x;
            bestt = make_pair(qry.y, i);
        }
    }

    out<<xormaxx<<" "<<(bestt.x + 1)<<" "<<bestt.y<<"\n";

    return 0;
}