Cod sursa(job #3318667)

Utilizator vlad7654vladimir manescu vlad7654 Data 28 octombrie 2025 13:39:48
Problema Xor Max Scor 75
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int LOG=21;
struct TRIE{
    struct Node{
        int apps;
        Node* sons[2];
    };
    Node* radacina=nullptr;
    void add(Node*& p, int x, int bit=LOG){
        if(p==nullptr){
            p=new Node();
        }
        p->apps++;
        if(bit<0){
            return;
        }
        int b=(x & (1 << bit)) > 0;
        add(p->sons[b], x, bit-1);
    }
    int query(Node*& p, int x, int bit=LOG){
        if(p==nullptr){
            return 0;
        }
        if(bit<0){
            return 0;
        }
        int b=(x & (1 << bit)) > 0;
        int preferabil=1-b;
        if(p->sons[preferabil]){
            return (1<<bit)+query(p->sons[preferabil], x, bit-1);
        }else{
            return query(p->sons[1-preferabil], x, bit-1);
        }
    }
};
int main(){
    int n, max1=-1, st, dr;
    fin>>n;
    vector<int> prefix(n+1, 0), v(n+1);
    TRIE trie;
    trie.add(trie.radacina, 0);
    for(int i=1;i<=n;i++){
        fin>>v[i];
        prefix[i]=(prefix[i-1]^v[i]);
        int verif=trie.query(trie.radacina, prefix[i]);
        if(max1<verif){
            max1=verif;
            dr=i;
        }
        trie.add(trie.radacina, prefix[i]);
    }

    for(int i=1;i<=n;i++){
        if((prefix[dr]^prefix[i-1])==max1){
            fout<<max1<<' '<<i<<' '<<dr;
            return 0;
        }
    }
}